Abo

TwoSum 相关问题思路总结

leetcode初见题,不能再熟悉,那K数之和呢?😐


wallhaven-g87m53

文章收录TwoSum的各种玩法

核心思想

这个问题的最基本形式是这样:给你一个数组和一个整数target,可以保证数组中存在两个数的和为target,请你返回这两个数的索引。

比如输入nums = [3,1,3,6],target = 6,算法应该返回数组[0,2],因为 3 + 3 = 6。

这个问题如何解决呢?首先最简单粗暴的办法当然是穷举了:

1

这个解法非常直接,时间复杂度 O(N^2),空间复杂度 O(1)。

更好一点的解法,可以通过一个哈希表减少时间复杂度:

2

这样,由于哈希表的查询时间为 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
解释:3424 相加得到 5858 小于 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 的类,使该类需要支持 addfind 的操作。

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 表的方法在时间上面更优。

代码实现

3

对于这个解法的时间复杂度呢,add方法是 O(1),find方法是 O(N),空间复杂度为 O(N),和上一道题目比较类似。

但是对于 API 的设计,是需要考虑现实情况的**。**比如说,我们设计的这个类,使用find方法非常频繁,那么每次都要 O(N) 的时间,岂不是很浪费费时间吗?对于这种情况,我们是否可以做些优化呢?

是的,对于频繁使用find方法的场景,我们可以进行优化。我们可以参考上一道题目的暴力解法,借助哈希集合来针对性优化find方法:

4

这样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;
/** Initialize your data structure here. */
public TwoSum() {
elements = new HashMap<>();
}
/** Add the number to an internal data structure.. */
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);
}
/** Find if there exists any pair of numbers which sum is equal to the value. */
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. 排序加双指针
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
// sort + two pointers
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. 哈希表
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
// HashSet
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]) { // S[i] < S[l] + S[r] && S[i] > S[r] > S[l]
result += r - l; // 直接加上可能的个数
r--;
} else {
l++;
}
}
}
return result;
}

四数之和

题目描述

题目来源于 LeetCode 上第 18 号问题: 四数之和。

给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 abcd ,使得 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,我们找到的答案是满足等式:

1
num1 + num2 = target

因此这个时候判断的时候,我们只需要判断 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, 但是这里就需要用到动态规划的知识了,暂不在这里讨论。