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;}
}