leetcode做题的笔记01 俩数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

这题有几种解法,其中一种比较优的解法是一次遍历+HashMap;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

另外,还有一种比较有趣的解法,如下,思路请见注释

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        //100000000000
        int volume =2048;
        //011111111111
        int bitMode = volume-1;
        //生成一个足够的的数组,数组内的值默认为0
        int [] result =new int[volume];

        //循环传入的数组
        for (int i=0;i<nums.length;i++){
            //对计算后的值进行与运行,作用是获取它在新数组的下标值
            //1.例如这题是target是9,传入的数组是{2, 7, 6, 11, 15, 5},第一个是2,(9-2)&bitmode = 7
            //4.第2此循环,第2个值是7,(9-7)&bitmode = 2
            int c = (target - nums[i]) & bitMode;
            //因为默认数组内的值为0,如果为0即说明没有
            //2.第一次循环时必定不进入
            //5.第二此循环时,有上一次循环可知,此时result[2]=1,进入if内部
            if (result[c]!=0){
                //由于下面插入result数组时+1,这里要-1
                //6.此时得出两数之和的下标
                return new int[]{result[c]-1,i};
            }
            //因为if处判断条件为是否为0,所以此次的值必须+1,
            //3.此时nums[0]=2,nums[i] & bitMode 为2,i=0,i+1=1,即result[2]=1
            result[nums[i] & bitMode]=i+1;
        }
        return null;
    }

    public static void main(String[] args) {
        int[] result = {2, 7, 6, 11, 15, 5};
        int target = 9;
        Solution  s = new Solution();
        int a[] = s.twoSum(result,target);
        if (a!=null){
            for (int oo:a) {
                System.out.println(oo);
            }
        }
    }
}

完~~