LC 15.三数之和
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 ≤ n u m s . l e n g t h ≤ 3000 3 \leq nums.length \leq 3000 3≤nums.length≤3000
- − 1 0 5 ≤ n u m s [ i ] ≤ 1 0 5 -10^5 \leq nums[i] \leq 10^5 −105≤nums[i]≤105
解法一(排序+双指针)
思路分析:
- 首先思考暴力求解,其时间复杂度为 O ( n 3 ) O(n^3) O(n3),同时还需要使用哈希表对所得元组进行去重,对此需要换一种思路来解决。
- 我们需要思考不重复的本质,对于一个三元组
[1, 2, 3]
,有六种排列情况,为了避免出现六种情况,可以对三个元素进行保证,即- 第二个元素不低于第一个元素
- 第三个元素不低于第一个元素
- 即保证三元组
[a, b, c]
,满足 a ≤ b ≤ c a \leq b \leq c a≤b≤c,如此在枚举三个元素时,可以保证不会出现重复的元组,即因为 a ≤ b ≤ c a \leq b \leq c a≤b≤c,不会出现枚举出[2, 3, 1]
的情况,即只会出现[1, 2, 3]
的情况 - 因此我们可以对题目给出数组
nums
进行排序,然后再去寻找满足条件的三元组,如此可避免重复情况,也方便排除重复的三元组 - 因为需要寻找满足
a
+
b
+
c
=
0
a + b + c = 0
a+b+c=0的三元组,因此对于暴力求解中的第二重循环和第三重循环,可以发现每当
b
从前往后枚举增加时,c
应该减少才能继续满足a+b+c = 0
的关系式 - 因此我们可以使用双指针,即当需要枚举数组的两个元素时,发现伴随第一个元素的递增,第二个元素是递减的,那么可以使用双指针(相向双指针),将枚举的时间复杂度由 O ( n 2 ) O(n^2) O(n2)减少至 O ( n ) O(n) O(n)
- 所以我们可以使用双指针来寻找
b
和c
,同时需要注意的是,需要一直保持左指针小于右指针,即保证 b ≤ c b \leq c b≤c,且当a+b+c > 0
时,说明c
的值过大,右指针需要向做移动,当a+b+c < 0
时,说明b的值较小,左指针需要向右移动;当找到对应元组,即a+b+c = 0
时,将元组保存到返回结果中,并移动左右指针 - 同时因为数组中会出现重复元素,即排序后这些重复元素会排列在一起,因此我们进行去重操作,如
if(i>0 && nums[i] == nums[i-1]) continue
实现代码如下:
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
Arrays.sort(nums); // 对数组元素进行排序
for (int i = 0; i < nums.length-2; ++i) { // 寻找元组的第一个数a
if (i > 0 && nums[i] == nums[i-1]) { // 跳过重复的数
continue;
}
int a = nums[i]; // 找到元组的第一个数a
// 寻找元组的第二个数b和第三个数c
int j = i+1;
int k = nums.length-1;
while (j < k) { // 相向双指针 遍历寻找
int s = a + nums[j] + nums[k];
if (s > 0) { // 说明 c 的值过大
-- k; // 移动右指针 往前继续寻找 c 即让c减小
} else if (s < 0) {
++ j; // 移动左指针 往后继续寻找 b
} else { // 找到符合条件的元组
List<Integer> list = new ArrayList<>();
list.add(a);
list.add(nums[j]);
list.add(nums[k]);
ans.add(list); // 将元组保存到返回值中
// 移动左指针
++ j;
while (j < k && nums[j] == nums[j-1]) // 跳过重复的数 避免重复添加相同的元组
++ j;
// 移动右指针
-- k;
while (j < k && nums[k] == nums[k+1]) // 跳过重复的数 避免重复添加相同元组
-- k;
}
}
}
return ans;
}
}
提交结果如下:
解答成功:
执行耗时:29 ms,击败了87.06% 的Java用户
内存消耗:50.4 MB,击败了16.79% 的Java用户
复杂度分析:
- 时间复杂度: O ( n 2 ) O(n^2) O(n2),对数组进行排序的时间复杂度为 O ( n l o g n ) O(nlog^n) O(nlogn),对数组进行遍历寻找元素的时间复杂度为 O ( n 2 ) O(n^2) O(n2),综合起来时间复杂度为 O ( n 2 ) O(n^2) O(n2)
- 空间复杂度: O ( 1 ) O(1) O(1),忽略排序所需要的空间,其余变量只使用了 O ( 1 ) O(1) O(1)的空间复杂度。
优化解法一(剪枝)
思路分析:
- 在将数组按照非递减顺序排序后,不难确定,当确定一个数a时
- 若
a
+
n
u
m
s
[
i
+
1
]
+
n
u
m
s
[
i
+
2
]
>
0
a + nums[i+1] + nums[i+2] > 0
a+nums[i+1]+nums[i+2]>0时,即a与右边相近的连续两个数相加结果大于0,那么a继续与后续的其他数相加,也一定大于0,所以此时已不存在满足
a + b + c = 0
的元组,那么可以直接break
退出循环。 - 同时若有
a
+
n
u
m
s
[
n
−
2
]
+
n
u
m
s
[
n
−
1
]
<
0
a + nums[n-2]+nums[n-1] < 0
a+nums[n−2]+nums[n−1]<0,即此时的a与数组中两个最大的元素相加 结果依然小于0,那么a与其他数组元素相加的结果依然会小于0,也不存在满足
a + b + c = 0
的元组,所以continue
继续往后遍历寻找a
优化代码如下:
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
Arrays.sort(nums); // 对数组元素进行排序
for (int i = 0; i < nums.length-2; ++i) { // 寻找元组的第一个数a
if (i > 0 && nums[i] == nums[i-1]) { // 跳过重复的数
continue;
}
int a = nums[i]; // 找到元组的第一个数a
if (a + nums[i+1] + nums[i+2] > 0) // 因为数组按非递减排序
break; // 若此时数组中连续三个数相加结果大于0 则后续不存在别的数使得a+b+c=0成立
if (a + nums[nums.length-2] + nums[nums.length-1] < 0)
continue; // 若此时a+数组中末尾两个最大的数结果小于0 则此时的a添加其他数依然会小于0
// 寻找元组的第二个数b和第三个数c
int j = i+1;
int k = nums.length-1;
while (j < k) { // 相向双指针 遍历寻找
int s = a + nums[j] + nums[k];
if (s > 0) { // 说明 c 的值过大
-- k; // 移动右指针 往前继续寻找 c 即让c减小
} else if (s < 0) {
++ j; // 移动左指针 往后继续寻找 b
} else { // 找到符合条件的元组
List<Integer> list = new ArrayList<>();
list.add(a);
list.add(nums[j]);
list.add(nums[k]);
ans.add(list); // 将元组保存到返回值中
// 移动左指针
++ j;
while (j < k && nums[j] == nums[j-1]) // 跳过重复的数 避免重复添加相同的元组
++ j;
// 移动右指针
-- k;
while (j < k && nums[k] == nums[k+1]) // 跳过重复的数 避免重复添加相同元组
-- k;
}
}
}
return ans;
}
}
提交结果如下:
解答成功:
执行耗时:25 ms,击败了99.46% 的Java用户
内存消耗:50.1 MB,击败了38.47% 的Java用户
复杂度分析:
- 时间复杂度: O ( n 2 ) O(n^2) O(n2)
- 空间复杂度: O ( 1 ) O(1) O(1)
注意
对于去重的代码,应该放在最后的添加到结果中,而不是移动左右指针便立马去重,考虑特殊情况,即数组为[0, 0, 0, 0, 0]
时
原文地址:https://blog.csdn.net/qq_61457746/article/details/140727076
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!