LeetCode 15 三数之和
题目:
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
提示：
3 <= nums.length <= 3000
-105 <= nums[i] <= 105
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解:
此题可使用暴力递归和回溯算法都可以解出此题,但是时间复杂度高,此处不给出具体解法
我们使用双指针法巧妙解决此问题,具体流程如下:
例：nums = [-2,-1,0,1,2,2,-1,3]
1.对数组排序
2.出现以下情况直接返回
a.数组为空
b.数组最小值大于0
c.数组最大值小于0
3.遍历数组，i为当前遍历的位置,定义L=i+1 R=数组长度-1，即L为i的下一位，R为数组末尾，然后我们按照以下步骤寻找:
a.如果nums[i]+nums[L]+nums[R]=0 记录结果且R左移L右移直至与当前L、R所在位置值不同的位置(此步骤就是去重操作)
b.如果nums[i]+nums[L]+nums[R]>0 说明和太大，R左移直至与当前R所在位置值不同的位置(此步骤就是去重操作)
c.如果nums[i]+nums[L]+nums[R]<0 说明和太小，L右移直至与当前L所在位置值不同的位置(此步骤就是去重操作)
d.一旦L，R相遇则此次循环结束
4.结果存储在数组list中
图解:
第一轮遍历
nums[i](-2)+nums[L](-1)+nums[R](3) = 0
记录下结果 [-2,-1,3]
此时list=[[-2,-1,3]]
L右移至与当前值不同的位置
R左移至与当前值不同的位置
nums[i](-2)+nums[L](0)+nums[R](2) = 0
记录下结果 [-2,0,2]
此时list=[[-2,-1,3],[-2,0,2]]
L右移至与当前值不同的位置
R左移至与当前值不同的位置
L,R相遇，循环结束，i右移至与当前位置值不同的位置开始下一轮循环
第二轮遍历
nums[i](-1)+nums[L](-1)+nums[R](3) = 1
和大于0，R左移至与当前值不同的位置
nums[i](-1)+nums[L](-1)+nums[R](2) = 0
记录下结果 [-1,-1,2]
此时list=[[-2,-1,3],[-2,0,2],[-1,-1,2]]
L右移至与当前值不同的位置
R左移至与当前值不同的位置
nums[i](-1)+nums[L](0)+nums[R](1) = 0
记录下结果 [-1,0,1]
此时list=[[-2,-1,3],[-2,0,2],[-1,-1,2],[-1,0,1]]
L右移至与当前值不同的位置
R左移至与当前值不同的位置
L,R相遇，循环结束，i右移至与当前位置值不同的位置开始下一轮循环
第三轮遍历
注意此时 nums[i](0)+nums[L](1) = 1
后续无论如何移动R将值减少也无法使和等于0，因此结束流程
返回结果
list=[[-2,-1,3],[-2,0,2],[-1,-1,2],[-1,0,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
| public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> listResult = new ArrayList<>();
Arrays.sort(nums);
if (nums.length <= 2 || nums[0] > 0 || nums[nums.length - 1] < 0) return listResult;
int preI = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) return listResult;
if (nums[i] == preI) continue;
preI = nums[i];
int L = i + 1;
int R = nums.length - 1;
while (L < R) {
if (nums[i] + nums[L] > 0) break;
int sum = nums[i] + nums[L] + nums[R];
if (sum == 0) {
listResult.add(Arrays.asList(nums[i], nums[L], nums[R]));
do {
L++;
} while (L < R && nums[L] == nums[L - 1]);
do {
R--;
} while (L < R && nums[R] == nums[R + 1]);
} else if (sum < 0) {
while (L < R && nums[i] + nums[L] + nums[R] < 0) {
L++;
}
} else {
while (L < R && nums[i] + nums[L] + nums[R] > 0) {
R--;
}
}
}
}
return listResult;
}
|