LeetCode 两数之和 + 三数之和

两数之和 简单题

思路：一个Map，key是数值，value是该数值对应的下标，遍历的时候判断一下当前数组下标对应的值在map里有没有可组合成target的（具体体现为在map里找target-nums【i】)，如果有，直接返回，没有的话就加进去，继续找。

需要掌握的方法：map的get和containsKey

cl
ass Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> m = new HashMap<>();
        m.put(nums[0],0);
        for(int i = 1;i<nums.length;++i){
            if(m.containsKey(target - nums[i])){
                return new int[]{m.get(target-nums[i]),i};
            }
            else{
                m.put(nums[i],i);
            }
        }
        return new int[0];
    }
}

三数之和 双指针 中等题

思路：严格上来说算三个指针，一个i是维护当前遍历到的数字下标，之后的l和r指针是从i所处位置开始，在i + 1 到len - 1这个区间中寻找nums[i]的相反数。

class Solution {
    // -4 -1 -1 0 1 2 
    // 
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        int len = nums.length;
        if(len < 2){
            return res;
        }
        for(int i = 0;i < len;++i){
            int l = i + 1;
            int r = len - 1;
            if( i != 0 && nums[i] == nums[i-1]){//与前一个数重复需要调过，不然会出现重复的三元组
                continue;
            }
            while(l < r){
                if(nums[i] + nums[l] + nums[r] == 0){
                    if(l > i + 1 && nums[l] == nums[l-1] ){//这里也是同理
                        l ++ ;
                        continue;
                    }
                    List<Integer> tmp = new ArrayList<>();
                    tmp.add(nums[i]);
                    tmp.add(nums[l]);
                    tmp.add(nums[r]);
                    l++;
                    r--;
                    //左右指针都要变，因为l变大的话，还希望结果有可能为0，r必须变小（意味着nums[r]变小)
                    res.add(tmp);
                }
                else if(nums[i] + nums[l] + nums[r] < 0){
                    //nums[l] 太小了，把它变大一点
                     l ++;
                }   
                else{
                    r --;
                }
            }
        }
        return res;
    }
}