【LBank交易平台】你真的会做 “2 Sum”题吗?
来源:小齐本齐
2 Sum 这题是 Leetcode 的第一题,相信大部分小伙伴都听过的吧。
作为一道标着 Easy 难度的题,它真的这么简单吗?
我在之前的刷题视频里说过,大家刷题一定要吃透一类题,为什么有的人题目做着越来越少,有的人总觉得刷不完的题,就是因为没有分类吃透。
单纯的追求做题数量是没有意义的,Leetcode 的题目只会越来越多,就像高三时的模考试卷一样做不完,但分类总结,学会解决问题的方式方法,才能遇到新题也不手足无措。
2 Sum
这道题题意就是,给一个数组和一个目标值,让你在这个数组里找到两个数,使得它俩之和等于这个目标值的。
比如题目中给的例子,目标值是 9,然后数组里 2 + 7 = 9
,于是返回 2 和 7 的下标。
方法一
在我多年前还不知道时空复杂度的时候,我想这还不简单嘛,就每个组合挨个试一遍呗,也就是两层循环。
后来我才知道,这样时间复杂度是很高的,是 O(n^2)
;但另一方面,这种方法的空间复杂度最低,是 O(1)
。
所以,面试时一定要先问面试官,是希望优化时间还是优化空间。
一般来说我们追求优化时间,但你不能默认面试官也是这么想的,有时候他就是想考你有没有这个意识呢。
如果一个方法能够兼具优化时间和空间那就更好了,比如斐波那契数列这个问题中从递归到 DP 的优化,就是时间和空间的双重优化,不清楚的同学后台回复「递归」快去补课~
我们来看下这个代码:
class Solution { public int[] twoSum(int[] nums, int target) { for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[i] + nums[j] == target) { return new int[]{i, j}; } } } return new int[]{-1, -1}; } }
-
时间复杂度:O(n^2)
-
空间复杂度:O(1)
喏,这速度不太行诶。
方法二
那在我学了 HashMap
这个数据结构之后呢,我又有了新的想法。
HashMap
或者 HashSet
的最大优势就是能够用 O(1)
的时间获取到目标值,那么是不是可以优化方法一的第二个循环呢?
有了这个思路,假设当前在看 x
,那就是需要把 x
之前或者之后的数放在 HashSet
里,然后看下 target - x
在不在这个 hashSet
里,如果在的话,那就匹配成功~
诶这里有个问题,这题要求返回这俩数的下标,可是 HashSet
里的数是无序的 ...
那就用升级版——HashMap
嘛~~还不了解 HashMap
的原理的同学快去公众号后台回复「HashMap」看文章啦。
HashMap
里记录下数值和它的 index
这样匹配成功之后就可以顺便得到 index
了。
这里我们不需要提前记录所有的值,只需要边过数组边记录就好了,为了防止重复,我们只在这个当前的数出现之前的数组部分里找另一个数。
总结一下,
-
HashMap
里记录的是下标i
之前的所有出现过的数; -
对于每个
nums[i]
,我们先检查target - nums[i]
是否在这个map
里; -
如果在就直接返回了,如果不在就把当前
i
的信息加进map
里。
class Solution { public int[] twoSum(int[] nums, int target) { int[] res = new int[2]; Map map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { if (map.containsKey(target - nums[i])) { res[0] = map.get(target - nums[i]); res[1] = i; return res; } map.put(nums[i], i); } return res; } }
-
时间复杂度:O(n)
-
空间复杂度:O(n)
喏,速度提升至 beat 99.96%
拓展
这是最基本的 2 Sum
问题,这个题可以有太多的变种了:
-
如果这个数组里有不止一组结果,要求返回所有组合,该怎么做?
-
如果这个数组里有重复元素,又该怎么做?
-
如果这个数组是一个排好序了的数组,那如何利用这个条件呢?- Leetcode 167
-
如果不是数组而是给一个
BST
,该怎么在一棵树上找这俩数呢?- Leetcode 653
...
这里讲一下排序数组这道题,之后会在 BST
的文章里会讲 653 这题。
排序数组
我们知道排序算法中最快的也需要 O(nlogn)
,所以如果是一个 2 Sum
问题,那没必要专门排序,因为排序会成为运算的瓶颈。
但如果题目给的就是个排好序了的数组,那肯定要好好收着了呀!
因为当数组是排好序的时候,我们可以进一步优化空间,达到 O(n)
的时间和 O(1)
的空间。
该怎么利用排好序这个性质呢?
那就是说,在 x
右边的数,都比 x
要大;在 x
左边的数,都比 x
要小。
-
如果
x + y > target
,那么就要y
往左走,往小的方向走; -
如果
x + y < target
,那么就要x
往右走,往大的方向走。
这也就是典型的 Two pointer
算法,两个指针相向而行的情况,我之后也会出文章详细来讲哒。
class Solution { public int[] twoSum(int[] numbers, int target) { int left = 0; int right = numbers.length - 1; while (left < right) { int sum = numbers[left] + numbers[right]; if (sum == target) { return new int[]{left + 1, right + 1}; //Your returned answers are not zero-based. } else if (sum < target) { left ++; } else { right --; } } return new int[]{-1, -1}; } }
3 Sum
3 Sum
的问题其实就是一个 2 Sum
的升级版,因为 1 + 2 = 3 嘛。。
那就是外面一层循环,固定一个值,在剩下的数组里做 2 Sum
问题。
反正 3 Sum
怎么着都得 O(n^2)
,就可以先排序,反正不在乎排序的这点时间了,这样就可以用 Two pointer
来做了。
还需要注意的是,这道题返回的是数值,而非 index
,所以它不需要重复的数值——The solution set must not contain duplicate triplets.
class Solution { public List> threeSum(int[] nums) { List> res = new ArrayList<>(); Arrays.sort(nums); for (int i = 0; i + 2 < nums.length; i++) { if (i > 0 && nums[i] == nums[i - 1]) { // skip same result continue; } int j = i + 1; int k = nums.length - 1; int target = -nums[i]; while (j < k) { if (nums[j] + nums[k] == target) { res.add(Arrays.asList(nums[i], nums[j], nums[k])); j++; k--; while (j < k && nums[j] == nums[j - 1]) { j++; // skip same result } while (j < k && nums[k] == nums[k + 1]) { k--; // skip same result } } else if (nums[j] + nums[k] > target) { k--; } else { j++; } } } return res; } }
4 Sum
最后就是 4 Sum
问题啦。
这一题如果只是 O(n^3)
的解法没什么难的,因为就是在 3 Sum
的基础上再加一层循环嘛。
但是如果在面试中只做出 O(n^3)
恐怕就过不了了哦😯
这 4 个数,可以想成两两的 2 Sum
,先把第一个 2 Sum
的结果存下来,然后在后续的数组中做第二个 2 Sum
,这样就可以把时间降低到 O(n^2)
了。
这里要注意的是,为了避免重复,也就是下图的 nums[x] + nums[y] + nums[z] + nums[k]
,其实和 nums[z] + nums[k] + nums[x] + nums[y]
并没有区别,所以我们要限制第二组的两个数要在第一组的两个数之后哦。
看下代码吧:
class Solution { public List> fourSum(int[] nums, int target) { Set> set = new HashSet<>(); Map>> map = new HashMap<>(); Arrays.sort(nums); // 先处理第一对,把它们的 sum 存下来 for(int i = 0; i < nums.length - 3; i++) { for(int j = i + 1; j < nums.length - 2; j++) { int currSum = nums[i] + nums[j]; List> pairs = map.getOrDefault(currSum, new ArrayList<>()); pairs.add(Arrays.asList(i, j)); map.put(currSum, pairs); } } // 在其后做 two sum for(int i = 2; i < nums.length - 1; i++) { for(int j = i + 1; j < nums.length; j++) { int currSum = nums[i] + nums[j]; List> prevPairs = map.get(target - currSum); if(prevPairs == 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); } }
好啦,以上就是 2 Sum
相关的所有问题啦。
- 免责声明
- 世链财经作为开放的信息发布平台,所有资讯仅代表作者个人观点,与世链财经无关。如文章、图片、音频或视频出现侵权、违规及其他不当言论,请提供相关材料,发送到:2785592653@qq.com。
- 风险提示:本站所提供的资讯不代表任何投资暗示。投资有风险,入市须谨慎。
- 世链粉丝群:提供最新热点新闻,空投糖果、红包等福利,微信:juu3644。