知一的指纹

15. 三数之和

题目

给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。

注意:答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]

解题思路

初读这道题时忽略了一个点,就是在检查时,如果有两个重复的数字可以都用上组成一个三元组集合,但是在返回结果的时候不能第一个数字参与组成三元组后第二个相同数字继续组成三元组。

有三种思路,先进性排序处理,然后再进行处理。第一种就是做三层枚举;第二种就是两层枚举,在进行 set O(1) 查找;第三种是一层枚举,然后从剩余列表中的左右两边进行查找,满足三元组的添加记录。

下面是主要介绍第三种思路的细节

  1. 排序处理
  2. 从第 0 位置开始遍历
    1. 分别取剩余数组的首尾值进行求和
    2. 如果大于零则向前移动尾部游标
    3. 如果小于零则向后移动头部游标
    4. 如果等于零则添加记录
      1. 添加记录后对首尾游标向中间移动一格
    5. 如果首尾游标没有相交则继续 2.1 步骤处理
  3. 进行下一位置的遍历,直到数组尾部
  4. 返回结果

整个流程思路基本是这样子的,然后我们对于边界情况的处理单独进行描述

  1. 如果当前遍历位置值大于 0 则直接返回结果
  2. 对于我在 ① 中描述的情况,需要在 2.1 之前进行与判断,当前位置与上一位置值相同则跳过,进行排重处理
  3. 同样的情况处理在 4.1 之后也要进行首尾游标移动方向相邻值的排重处理

解题思维

  1. 首先需要做到的是充分理解题意,至少要做到能肉眼推导正确结果。
  2. 解决方案一般都会有多种,合理选择最优方案进行骨架设计 ②,充分考虑时间和空间复杂度。
  3. 然后解决边界条件 ③,优化代码可读性。
  4. 充分进行测试验证算法的正确性。

解题代码

最后放一下解题代码,也是参考别人的方案实现的:

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
import java.util.*;

public class ThreeSum {

public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> resp = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) break;
int l = i + 1;
int r = nums.length - 1;
if (i > 0 && nums[i-1] == nums[i]) continue;
while (l < r){
int sum = nums[i] + nums[l] + nums[r];
if ( sum> 0) r--;
else if (sum < 0) l++;
else if (sum == 0){
resp.add(Arrays.asList(nums[i], nums[l] , nums[r]));
while (l < r && nums[l] == nums[l+1]) l++;
while (l < r && nums[r] == nums[r-1]) r--;
l++;
r--;
}
}
}
return resp;
}
}
noogel wechat
文章会同步推送到公众号,欢迎关注!
如果此文章能给您带来小小的提升,不妨小额赞赏我一下,以鼓励我写出更好的文章!