两数之和三数之和四数之和

宋正兵 on 2021-04-19

最近刷题遇到了好几次这个类型的题,于是在此做个总结。

两数之和

两数之和

利用 Map 来进行记录和快速查找

题目大意:给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 的那 两个 整数,并返回它们的数组下标。

思路:我们只讨论最优解,一次遍历就能够找到这两个数。我们利用 Map 来存放已经遍历过的数字和其对应的下标。对于当前遍历到的第 i 个数字,如果我们能够在 Map 的中找到 key 为 target-nums[i] 的数据,说明找到了那两个整数,返回它们的下标即可。

时间复杂度:$O(N)$,其中 $N$ 是数组中元素的个数。对于每一个元素 x,我们可以 $O(1)$ 地寻找 target-x

代码:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++) {
if (hashtable.containsKey(target - nums[i])) {
return new int[] {hashtable.get(target - nums[i]), i};
}
hashtable.put(nums[i], i);
}
return new int[0];
}
}

三数之和

先对数组进行排序,固定其中一个指针指向数字 base,再用双指针在 base 之后的区域内寻找合适的位置

三数之和

题目大意:给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0且不重复的三元组。

思路:

  1. 对数组进行排序
  2. 遍历排序后的数组:
    1. nums[i] > 0:因为是排序后的数组,所以不可能有三个数之和等于0,直接返回结果;
    2. nums[i] == nums[i - 1]:跳过,避免出现重复解;
    3. 令左指针 l = i + 1,右指针 r = nums.length - 1,当 l < r 时执行循环:
      • nums[i] + nums[l] + nums[r] == 0,执行循环,跳过左边界和右边界上重复的元素,避免重复解,同时将 lr 移动到下一位置,寻找新的解;
      • nums[i] + nums[l] + nums[r] > 0,说明 nums[r] 太大,右边界 r 左移;
      • nums[i] + nums[l] + nums[r]< 0,说明 nums[l] 太小,左边界 l 右移;

时间复杂度:$O(N^{2})$,其中 $N$ 是数组的长度。数组排序 $O(NlogN)$,遍历数组 $O(N)$,双指针遍历 $O(N)$,总体时间复杂度为 $O(NlogN) + 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
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> resList = new ArrayList<List<Integer>>();
if (nums == null || nums.length < 3) {
return resList;
}
Arrays.sort(nums);
// 根据每个nums[i]去找另外的两个数字
for (int i = 0; i < nums.length; i++) {
// 如果当前数字大于0,则三数之和一定大于0,所以结束循环
if (nums[i] > 0) {
break;
}
// 去重
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// nums[i] + nums[l] + nums[r] == 0
int l = i + 1, r = nums.length - 1;
while (l < r) {
int temp = nums[i] + nums[l] + nums[r];
if (temp == 0) {
resList.add(Arrays.asList(nums[i], nums[l], nums[r]));
// 去重,以nums[i]开头的三元组中不再包含当前值
while(l < r && nums[l + 1] == nums[l]) {
l++;
}
while(l < r && nums[r - 1] == nums[r]) {
r--;
}
l++;
r--;
} else if (temp < 0) {
// 说明nums[l]太小,需要找一个更大的元素
l++;
} else {
// 说明nums[n]太大,需要找一个更小的元素
r--;
}
}
}
return resList;
}
}

四数之和

和三数之和类似,只不过是固定了前两个指针,然后利用双指针移动来寻找满足条件的解。

四数之和

题目大意:给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target相等?找出所有满足条件且不重复的四元组。

思路:

  1. 对数组进行排序
  2. 两层 for 遍历排序后的数组:
    1. nums[i] + nums[j] + nums[nums.length - 2] + nums[nums.length - 1] < target,当前组合所能产生的最大值小于 target,跳过;
    2. nums[i] == nums[i - 1] 或者 nums[j] == nums[j - 1],跳过,避免出现重复解;
    3. 令左指针 l = j + 1,右指针 r = nums.length - 1,当 l < r 时执行循环:
      • nums[i] + nums[j] + nums[l] + nums[r] == target,执行循环,跳过左边界和右边界上重复的元素,避免重复解,同时将 lr 移动到下一位置,寻找新的解;
      • nums[i] + nums[j] + nums[l] + nums[r] > target,说明 nums[r] 太大,右边界 r 左移;
      • nums[i] + nums[j] + nums[l] + nums[r] < target,说明 nums[l] 太小,左边界 l 右移;

时间复杂度:$O(N^{3})$,其中 $N$ 是数组的长度。排序的时间复杂度是 $O(NlogN)$,枚举四元组的时间复杂度是 $O(N^{3})$,因此总时间复杂度是 $O(NlogN + N^{3})$

代码:

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
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> list = new ArrayList<>();
if (nums == null || nums.length < 4) {
return list;
}
Arrays.sort(nums);
for (int i = 0; i < nums.length - 3; i++) {
// 剪枝,去除重复
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
for (int j = i + 1; j < nums.length - 2; j++) {
// 剪枝,去除重复
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
int l = j + 1, r = nums.length - 1;
while (l < r) {
int sum = nums[i] + nums[j] + nums[l] + nums[r];
if (sum == target) {
list.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));
// 去重,以nums[i]开头的四元组中不再包含当前值
while(l < r && nums[l + 1] == nums[l]) {
l++;
}
l++;
while(l < r && nums[r - 1] == nums[r]) {
r--;
}
r--;
} else if (sum < target) {
// 说明nums[l]太小,需要找一个更大的元素
l++;
} else {
// 说明nums[n]太大,需要找一个更小的元素
r--;
}
}
}
}
return list;
}
}