你真的会做2Sum吗？

这也就是典型的 Two pointer 算法&＃xff0c;两个指针相向而行的情况&＃xff0c;我之后也会出文章详细来讲哒。

class Solution {public int[] twoSum(int[] numbers, int target) {int left &＃61; 0;int right &＃61; numbers.length - 1;while (left < right) {int sum &＃61; numbers[left] &＃43; numbers[right];if (sum &＃61;&＃61; target) {return new int[]{left &＃43; 1, right &＃43; 1}; //Your returned answers are not zero-based.} else if (sum < target) {left &＃43;&＃43;;} else {right --;}}return new int[]{-1, -1};}
}


3 Sum

3 Sum 的问题其实就是一个 2 Sum 的升级版&＃xff0c;因为 1 &＃43; 2 &＃61; 3 嘛。。

那就是外面一层循环&＃xff0c;固定一个值&＃xff0c;在剩下的数组里做 2 Sum 问题。

反正 3 Sum 怎么着都得 O(n^2) &＃xff0c;就可以先排序&＃xff0c;反正不在乎排序的这点时间了&＃xff0c;这样就可以用 Two pointer 来做了。

还需要注意的是&＃xff0c;这道题返回的是数值&＃xff0c;而非 index&＃xff0c;所以它不需要重复的数值——The solution set must not contain duplicate triplets.

class Solution {public List> threeSum(int[] nums) {List> res &＃61; new ArrayList<>();Arrays.sort(nums);for (int i &＃61; 0; i &＃43; 2 < nums.length; i&＃43;&＃43;) {if (i > 0 && nums[i] &＃61;&＃61; nums[i - 1]) {// skip same resultcontinue;}int j &＃61; i &＃43; 1;int k &＃61; nums.length - 1;  int target &＃61; -nums[i];while (j < k) {if (nums[j] &＃43; nums[k] &＃61;&＃61; target) {res.add(Arrays.asList(nums[i], nums[j], nums[k]));j&＃43;&＃43;;k--;while (j < k && nums[j] &＃61;&＃61; nums[j - 1]) {j&＃43;&＃43;;  // skip same result}while (j < k && nums[k] &＃61;&＃61; nums[k &＃43; 1]) {k--;  // skip same result}} else if (nums[j] &＃43; nums[k] > target) {k--;} else {j&＃43;&＃43;;}}}return res;}
}


4 Sum

最后就是 4 Sum 问题啦。

这一题如果只是 O(n^3) 的解法没什么难的&＃xff0c;因为就是在 3 Sum 的基础上再加一层循环嘛。

但是如果在面试中只做出 O(n^3) 恐怕就过不了了哦????

这 4 个数&＃xff0c;可以想成两两的 2 Sum&＃xff0c;先把第一个 2 Sum 的结果存下来&＃xff0c;然后在后续的数组中做第二个 2 Sum&＃xff0c;这样就可以把时间降低到 O(n^2) 了。

这里要注意的是&＃xff0c;为了避免重复&＃xff0c;也就是下图的 nums[x] &＃43; nums[y] &＃43; nums[z] &＃43; nums[k] &＃xff0c;其实和 nums[z] &＃43; nums[k] &＃43; nums[x] &＃43; nums[y] 并没有区别&＃xff0c;所以我们要限制第二组的两个数要在第一组的两个数之后哦。

看下代码吧&＃xff1a;

class Solution {public List> fourSum(int[] nums, int target) {Set> set &＃61; new HashSet<>();Map>> map &＃61; new HashMap<>();Arrays.sort(nums);// 先处理第一对&＃xff0c;把它们的sum存下来for(int i &＃61; 0; i < nums.length - 3; i&＃43;&＃43;) {for(int j &＃61; i &＃43; 1; j < nums.length - 2; j&＃43;&＃43;) {int currSum &＃61; nums[i] &＃43; nums[j];List> pairs &＃61; map.getOrDefault(currSum, new ArrayList<>());pairs.add(Arrays.asList(i, j));map.put(currSum, pairs);}}// 在其后做two sumfor(int i &＃61; 2; i < nums.length - 1; i&＃43;&＃43;) {for(int j &＃61; i &＃43; 1; j < nums.length; j&＃43;&＃43;) {int currSum &＃61; nums[i] &＃43; nums[j];List> prevPairs &＃61; map.get(target - currSum);if(prevPairs &＃61;&＃61; null) {continue;}for(List pair : prevPairs) {if(pair.get(1) < i) {set.add(Arrays.asList(nums[pair.get(0)], nums[pair.get(1)], nums[i], nums[j]));}}}}return new ArrayList<>(set);}
}


好啦&＃xff0c;以上就是 2 Sum 相关的所有问题啦&＃xff0c;如果有收获的话&＃xff0c;记得给我点个赞哦&＃xff5e;

---

爱分享&＃xff0c;爱开源&＃xff0c;GitHubPorn 现已正式上线&＃xff01;专注于为大家分享优质的计算机学习资源与开发者工具。

如果今天的推荐符合你的口味&＃xff0c;请在文章点赞&＃xff0c;以表示对我的支持&＃xff0c;你们的点赞和转发关注&＃xff0c;是我持续更新的动力^_^