15. 三数之和

题目描述

原题
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例 1:
1
输入:nums = [-1,0,1,2,-1,-4]
2
输出:[[-1,-1,2],[-1,0,1]]
Copied!
示例 2:
1
输入:nums = []
2
输出:[]
Copied!
示例 3:
1
输入:nums = [0]
2
输出:[]
Copied!
提示:
    0 <= nums.length <= 3000
    -105 <= nums[i] <= 105

题解

1
class Solution {
2
public List<List<Integer>> threeSum(int[] nums) {
3
int n = nums.length;
4
Arrays.sort(nums);
5
List<List<Integer>> ans = new ArrayList<List<Integer>>();
6
// 枚举 a a的值必须小于0
7
// a <= b <= c
8
for (int first = 0; first < n && nums[first] <=0; ++first) {
9
// 需要和上一次枚举的数不相同 相等则跳出本次循环
10
if (first > 0 && nums[first] == nums[first - 1]) {
11
continue;
12
}
13
// c 对应的指针初始指向数组的最右端
14
int third = n - 1;
15
int target = -nums[first];
16
// 枚举 b
17
for (int second = first + 1; second < n; ++second) {
18
// 需要和上一次枚举的数不相同
19
if (second > first + 1 && nums[second] == nums[second - 1]) {
20
continue;
21
}
22
// 需要保证 b 的指针在 c 的指针的左侧
23
//循环找到满足相加等0的最大third值 注意这里的second没有变化
24
while (second < third && nums[second] + nums[third] > target) {
25
--third;
26
}
27
// 如果指针重合,随着 b 后续的增加
28
// 就不会有满足 a+b+c=0 并且 b<c 的 c 了,可以退出循环
29
if (second == third) {
30
break;
31
}
32
if (nums[second] + nums[third] == target) {
33
List<Integer> list = new ArrayList<Integer>();
34
list.add(nums[first]);
35
list.add(nums[second]);
36
list.add(nums[third]);
37
ans.add(list);
38
}
39
}
40
}
41
return ans;
42
}
43
}
Copied!
最近更新 3mo ago
复制链接