leetcode初见题,不能再熟悉,那K数之和呢?😐
文章收录TwoSum的各种玩法
核心思想 这个问题的最基本形式 是这样:给你一个数组和一个整数target
,可以保证数组中存在 两个数的和为target
,请你返回这两个数的索引。
比如输入nums = [3,1,3,6],target = 6
,算法应该返回数组[0,2]
,因为 3 + 3 = 6。
这个问题如何解决呢?首先最简单粗暴的办法当然是穷举了:
这个解法非常直接,时间复杂度 O(N^2),空间复杂度 O(1)。
更好一点的解法,可以通过一个哈希表减少时间复杂度:
这样,由于哈希表的查询时间为 O(1),算法的时间复杂度降低到 O(N),但是需要 O(N) 的空间复杂度来存储哈希表。不过综合来看,是要比暴力解法高效的。
我觉得 Two Sum 系列问题就是想教我们如何使用哈希表处理问题 。我们接着往后看。
两种思路 对于 TwoSum 类问题,总的来说有两种大的方向,一种方向是借助 Hash 表 ,另外一种是借助排序,然后利用相向双指针 来解决问题,我们分别来看看:
Hash表 1 2 3 4 5 6 7 8 9 10 11 public int [] twoSum(int [] nums, int target) { Map<Integer, Integer> remainValues = new HashMap<>(); for (int i = 0 ; i < nums.length; ++i) { if (remainValues.containsKey(target - nums[i])) { int anotherIndex = remainValues.get(target - nums[i]); return new int [] {i, anotherIndex}; } remainValues.put(nums[i], i); } return new int [] {-1 , -1 }; }
思路很简单,遍历数组,每访问一个元素,先判断其配对的元素是否在 Hash 表中,如果在的话就说明我们找到了答案,将其输出即可,如果没有找到,就将当前的元素放入 Hash 表中,以方便后面的元素来配对。
这里因为题目要求输出元素在数组中的位置,所以用 HashMap 来存储访问过的元素和其对应的 index。
我们再来分析一下其时空复杂度。
由于使用了 Hash 表,空间复杂度是 O(n) 的,另外就是最差的情况,数组中的每个元素都要遍历到,因此时间复杂度也是 O(n) 。
从时间上面来看,这个算法肯定是最优的,这很好理解,你要在数组中寻找配对的答案,数组当中的数肯定都需要看一遍。
排序加双指针的思路 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 public int [] twoSum(int [] n, int t) { if (n == null || n.length == 0 ) { return new int [0 ]; } Arrays.sort(n); int [] result = new int [2 ]; int l = 0 , r = n.length - 1 ; while (l < r) { if (n[l] + n[r] == t) { result[0 ] = n[l]; result[1 ] = n[r]; return result; } else if (n[l] + n[r] < t) { l++; } else { r--; } } return new int [0 ]; }
这种思路的前提是题目没有要求我们必须输出元素在数组中的位置,因为排序会改变元素在数组中的位置,这里,我们输出元素本身即可。
这里的思路就是一头一尾两个指针。
每次判断的时候,我们将左右两个指针指向的元素加起来的和与我们要找的 target 对比,如果比 target 小,也就是说明如果在左指针不变的情况下,左指针加上左右指针中间的任意一个元素都会比 target 小,这也说明左指针不可能是我们要找的答案,因此向右移动左指针。
如果是加起来和我们要找的 target 对比,比 target 大,分析类似,这时需要将右指针向左移动。
我们来看看这里的时间复杂度,因为做了排序这么一个操作,其时间复杂度就会是O(nlgn) ,对于空间复杂度来说,这里并没有使用额外的空间,因此空间复杂度是常数级的 O(1) 。
你有没有想过这两种方法分别比较适合什么样的情况呢,基于 TwoSum 问题,思考下面的变化:
如果题目要求输出所有可能的答案,该怎么处理?
如果题目要求输出所有可能的答案,并且数组中有重复元素该怎么处理?
如果题目要求找到比 target 小/大 的配对该怎么处理?
如果要找出两数之差等于 target 的配对,该如何进行?
TwoSum 的解题思路是否可以拓展到 TreeSum 或者更多的配对?
上面的问题可能有些你曾想过,有些没有,那么就让我们带着上述的问题来看看具体的例题,熟练地将上述两种方法应用到实际的题目中去。
变形题目分析 返回所有可能情况 题目描述 题目还是 TwoSum,但是这时需要你返回所有可能的情况(不重复),并且数组中允许重复元素的出现。
思考 首先我们需要思考的是,使用之前提到的两种方法中的哪一种会比较好。
是不是两种方法都可以,你分析一下会发现其实两种方法都是可行的,和之前的 TwoSum 不一样的是,这时当找到答案后,需要继续寻找,而不是直接返回 。
但是由于数组中存在重复元素,因此两种方法里面都需要考虑去重的机制。
对于 Hash 表的方法来说,其实你并不清楚之前是否添加过相同的答案,因此我们考虑使用一个集合去存储答案,保证答案的不重复性;
对于排序的方法来说,去重的方式有所不同,排完序后,相同的元素会挨在一起,对于之前考虑过的元素,我们只需要略过就行,指针的移动很好地保证了这一点。
这里就展示排序实现的方法:
代码实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 public List<int []> twoSum6(int [] nums, int target) { if (nums == null || nums.length < 2 ) return 0 ; Arrays.sort(nums); List<int []> results = new ArrayList<>(); int left = 0 , right = nums.length - 1 ; while (left < right) { int v = nums[left] + nums[right]; if (v == target) { int [] result = {nums[left], nums[right]}; results.add(result); left++; right--; while (left < right && nums[right] == nums[right + 1 ]) { right--; } while (left < right && nums[left] == nums[left - 1 ]){ left++; } } else if (v > target) { right--; } else { left++; } } return results; }
小于 K 的两数之和 题目描述 给你一个整数数组 A
和一个整数 K
,请在该数组中找出两个元素,使它们的和小于 K
但尽可能地接近 K
,返回这两个元素的和 。
如不存在这样的两个元素,请返回 -1
。
示例 1:
1 2 3 输入:A = [34 ,23 ,1 ,24 ,75 ,33 ,54 ,8 ], K = 60 输出:58 解释:34 和 24 相加得到 58 ,58 小于 60 ,满足题意。
示例 2:
1 2 3 输入:A = [10 ,20 ,30 ], K = 15 输出:-1 解释:我们无法找到和小于 15 的两个元素。
思考 传统的 TwoSum 都是要你找到等于 target 的配对,那么如果说要找到 大于/小于 target 的配对呢?
这个时候 Hash 表的方法就很难 work 了,因为 Hash 表比较适合处理 等于 的情况 !
那么就需要考虑如何使用排序加双指针的方法来解决这个问题,这里,题目是要求小于 target 的数量 ,我们还是按照之前的分析思路来分析。
如果说当前左右指针指向的元素的和大于或者等于 target,那么势必我们需要向左移动右指针,让两个元素的和尽可能地小,当前头尾指针指向的元素和小于 target 的时候,这时我们需要记录答案,虽然这道题目里面没提,如果说要记录配对数量的话,这时并不是记录一个答案,如果说当前左指针固定,除了当前的右指针指向的元素,在左指针和右指针之间的数都是满足要求的,我们只需要加上这个区间的数量即可,当然如果数组中存在重复元素,那么我们就需要按照之前的套路遍历去重了,当然对于这道题来说,我们选择满足条件的最大值即可。
代码实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 public int twoSumLessThanK (int [] A, int K) { if (A == null || A.length == 0 ) { return -1 ; } Arrays.sort(A); int l = 0 , r = A.length - 1 ; int result = Integer.MIN_VALUE; while (l < r) { if (A[l] + A[r] >= K) { r--; } else { result = Math.max(result, A[l] + A[r]); l++; } } return result == Integer.MIN_VALUE ? -1 : result; }
两数之和 III 题目描述 设计并实现一个 TwoSum 的类,使该类需要支持 add
和 find
的操作。
add
操作 - 对内部数据结构增加一个数。find
操作 - 寻找内部数据结构中是否存在一对整数,使得两数之和与给定的数相等。
示例 1:
1 2 3 add(1 ); add(3 ); add(5 ); find(4 ) -> true find(7 ) -> false
示例 2:
1 2 3 add(3 ); add(1 ); add(2 ); find(3 ) -> true find(6 ) -> false
思考 题目要求让你实现一个数据结构,这个结构支持 “添加元素 ” 和 “TwoSum ” 两个功能。
这时你需要综合两种方法的优劣性来选择。
首先是 Hash 表的方法,如果使用这个方法,我们不需要考虑太多的东西,元素来了直接扔进数组就行,也就是说 添加元素 操作只需要 O(1) 的时间复杂度就可以完成,但是TwoSum 的完成需要额外 O(n) 的空间;
再来看看排序的方法,因为这里插入元素我们需要保证元素有序,因此 添加元素 需要 O(n) 的时间,但是这里 TwoSum 操作并不需要额外空间,综合来考虑,因为 添加元素 和 TwoSum 操作都会比较频繁,因此 Hash 表的方法在时间上面更优。
代码实现 ①
对于这个解法的时间复杂度呢,add
方法是 O(1),find
方法是 O(N),空间复杂度为 O(N),和上一道题目比较类似。
但是对于 API 的设计,是需要考虑现实情况的** 。**比如说,我们设计的这个类,使用find
方法非常频繁,那么每次都要 O(N) 的时间,岂不是很浪费费时间吗?对于这种情况,我们是否可以做些优化呢?
是的,对于频繁使用find
方法的场景,我们可以进行优化。我们可以参考上一道题目的暴力解法,借助哈希集合 来针对性优化find
方法:
这样sum
中就储存了所有加入数字可能组成的和,每次find
只要花费 O(1) 的时间在集合中判断一下是否存在就行了,显然非常适合频繁使用find
的场景。
②
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 private Map<Integer, Integer> elements;private int MAX_VALUE = Integer.MIN_VALUE;private int MIN_VALUE = Integer.MAX_VALUE;public TwoSum () { elements = new HashMap<>(); } public void add (int number) { elements.put(number, elements.getOrDefault(number, 0 ) + 1 ); MAX_VALUE = Math.max(MAX_VALUE, number); MIN_VALUE = Math.min(MIN_VALUE, number); } public boolean find (int value) { if (value < 2 * MIN_VALUE || value > 2 * MAX_VALUE) { return false ; } for (int i : elements.keySet()) { if (i * 2 == value && elements.get(i) >= 2 ) { return true ; } else if (i * 2 != value && elements.containsKey(value - i)) { return true ; } } return false ; }
三数之和 题目描述 题目来源于 LeetCode 上第 15 号问题: 三数之和。
给定一个包含 n 个整数的数组 nums
,判断 nums
中是否存在三个元素 a,b,c , 使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。
注意: 答案中不可以包含重复的三元组。
1 2 3 4 5 6 例如, 给定数组 nums = [-1 , 0 , 1 , 2 , -1 , -4 ], 满足要求的三元组集合为: [ [-1 , 0 , 1 ], [-1 , -1 , 2 ] ]·
思考 三数之和,Hash 表以及排序的思路都是可行的。
但是这里涉及到去重,这里比较推荐的做法是排序加双指针。
思路其实比较直观,确定一个元素,然后去找另外两个元素,这么一来就把 3Sum 转变成了 2Sum 的问题,这里我两个方法都实现了一下,你可以进行参考。
代码实现
排序加双指针
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 public List<List<Integer>> threeSum(int [] nums) { if (nums == null || nums.length < 3 ) { return new ArrayList<>(); } Arrays.sort(nums); List<List<Integer>> results = new ArrayList<>(); for (int i = 0 ; i < nums.length - 2 ; ++i) { if ((i != 0 ) && (nums[i] == nums[i - 1 ])) { continue ; } List<Integer> result = new ArrayList<>(); twoSum(results, nums, i + 1 , -nums[i]); result = null ; } return results; } private void twoSum (List<List<Integer>> results, int [] nums, int startIndex, int target) { int left = startIndex, right = nums.length - 1 ; while (left < right) { if (nums[left] + nums[right] > target) { right--; } else if (nums[left] + nums[right] < target) { left++; } else { List<Integer> result = new ArrayList<>(); result.add(-target); result.add(nums[left]); result.add(nums[right]); results.add(result); left++; right--; while ((left < right) && (nums[left - 1 ] == nums[left])) { left++; } while ((right > left) && (nums[right + 1 ] == nums[right])) { right--; } } } }
哈希表
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 public List<List<Integer>> threeSum(int [] nums) { if (nums == null || nums.length < 3 ) { return new ArrayList<>(); } Arrays.sort(nums); Set<List<Integer>> resultsSet = new HashSet<>(); List<List<Integer>> results = new ArrayList<>(); for (int i = 0 ; i < nums.length - 2 ; ++i) { if ((i != 0 ) && (nums[i - 1 ] == nums[i])) { continue ; } Set<Integer> existedValue = new HashSet<>(); for (int j = i + 1 ; j < nums.length; ++j) { if (!existedValue.contains(nums[j])) { existedValue.add(-nums[j] - nums[i]); } else { List<Integer> result = new ArrayList<>(); Collections.addAll(result, nums[i], -nums[j] - nums[i], nums[j]); resultsSet.add(result); } } existedValue = null ; } results.addAll(resultsSet); return results; }
有效三角形个数 题目描述 题目来源于 LeetCode 上第 611 号问题:有效三角形的个数。
给定一个包含非负整数的数组,你的任务是统计其中可以组成三角形三条边的三元组个数。
示例 1:
1 2 3 4 5 6 7 输入: [2 ,2 ,3 ,4 ] 输出: 3 解释: 有效的组合是: 2 ,3 ,4 (使用第一个 2 )2 ,3 ,4 (使用第二个 2 )2 ,2 ,3
注意:
数组长度不超过1000。
数组里整数的范围为 [0, 1000]。
思考 题目要求选出三条边,使得这三条边能够构成三角形,咋眼看上去这道题貌似和 TwoSum 没啥关系。
但我们回顾一下中学时期学的东西,三边构成三角形的条件是 任意两边之和大于第三边 ,那是不是说我们需要把三条边都组合配对考虑一下?其实不用,我们可以得出下面的结论
1 a < b < c && a + b > c => 三角形
如果已知三条边的大小顺序,那么其实我们只需要比较一次 即可。
你再看看这是不是我们熟悉的 TwoSum 变种问题 - 如果题目要求找到比 target 小/大 的配对该怎么处理?
这个时候我们从右往左选定 c ,然后使用 TwoSum 来找出 a 、b 即可,由于题目只要求输出个数,那么就按照之前讲的思路,直接相加即可。
代码实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public int triangleCount (int [] S) { if (S == null || S.length == 0 ) { return 0 ; } Arrays.sort(S); int result = 0 ; for (int i = S.length - 1 ; i >= 2 ; --i) { int l = 0 , r = i - 1 ; while (l < r) { if (S[i] < S[l] + S[r]) { result += r - l; r--; } else { l++; } } } return result; }
四数之和 题目描述 题目来源于 LeetCode 上第 18 号问题: 四数之和。
给定一个包含 n 个整数的数组 nums
和一个目标值 target
,判断 nums
中是否存在四个元素 a ,b ,c 和 d ,使得 a + b + c + d 的值与 target
相等?找出所有满足条件且不重复的四元组。
注意:
答案中不可以包含重复的四元组。
示例:
1 2 3 4 5 6 7 8 给定数组 nums = [1 , 0 , -1 , 0 , -2 , 2 ],和 target = 0 。 满足要求的四元组集合为: [ [-1 , 0 , 0 , 1 ], [-2 , -1 , 1 , 2 ], [-2 , 0 , 0 , 2 ] ]
思考 4Sum 的思路和 3Sum 的思路是一样的,只不过这时我们需要先将其转换成 3Sum 来处理,其实就是比 3Sum 多了一次选择。
原先是三数之和为0,然后转化成c = -a-b 的形式
现在是四数之和为target,也是类似的做法,不简单😷
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 public List<List<Integer>> fourSum(int [] nums, int target) { if (nums.length < 4 ) { return new ArrayList<>(); } Arrays.sort(nums); List<List<Integer>> results = new ArrayList<>(); for (int i = 0 ; i < nums.length - 3 ; ++i) { if (i != 0 && nums[i] == nums[i - 1 ]) { continue ; } List<List<Integer>> subResults = threeSum(nums, i + 1 , target - nums[i]); for (List<Integer> res : subResults) { res.add(nums[i]); results.add(res); } } return results; } private List<List<Integer>> threeSum(int [] nums, int start, int target) { List<List<Integer>> results = new ArrayList<>(); for (int i = start; i < nums.length - 2 ; ++i) { if (i != start && nums[i] == nums[i - 1 ]) { continue ; } List<List<Integer>> res = twoSum(nums, i + 1 , target - nums[i]); for (List<Integer> r : res) { r.add(nums[i]); results.add(r); } } return results; } private List<List<Integer>> twoSum(int [] nums, int start, int target) { List<List<Integer>> results = new ArrayList<>(); int l = start, r = nums.length - 1 ; while (l < r) { if (nums[l] + nums[r] < target) { l++; } else if (nums[l] + nums[r] > target) { r--; } else { List<Integer> result = new ArrayList<>(); result.add(nums[l]); result.add(nums[r]); results.add(result); r--; l++; while (l < r && nums[r] == nums[r - 1 ]) { r--; } while (l < r && nums[l] == nums[l + 1 ]) { l++; } } } return results; }
两数之差 题目描述 给定一个 target,求出两数之差等于 target 的情况。
思考 如果使用 Hash 表的做法,对于传统的 TwoSum,我们找到的答案是满足等式:
因此这个时候判断的时候,我们只需要判断 target - nums
在不在 Hash 表中即可,对于两数之差的话,我们找到的答案是满足等式:
1 num1 - num2 = target or num2 - num1 = target
在这种情况下,我们需要判断 target + num
以及 num - target
即可,也就是相比之前,判断条件不同且多了一个。
如果是使用排序加双指针的方法呢?这其实是个打破思路局限的很好例子,这个时候我们需要用到同向双指针了,两个指针均从左向右移动,一前一后,用右边的减去左边的差值来和 target 做比较,如果小了,移动右指针,大了,移动左指针,等于,输出答案。
代码实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 public int [] twoDiff(int [] n, int t) { if (n == null || n.length == 0 ) { return new int [0 ]; } Arrays.sort(n); int [] result = new int [2 ]; int l = 0 , r = 1 ; while (r < n.length) { if (l == r) { r++; } if (n[r] - n[l] == t) { result[0 ] = n[l]; result[1 ] = n[r]; return result; } else if (n[r] - n[l] < t) { r++; } else { l++; } } return new int [0 ]; }
总结 TwoSum 相关的问题就分析到这里,非常有趣的一点是,TwoSum 不仅可以扩展成 3Sum,4Sum,它也可以扩展为 KSum, 但是这里就需要用到动态规划 的知识了,暂不在这里讨论。