LeetCode.015.3Sum 三数之和
题目描述
15 3Sum
https://leetcode-cn.com/problems/3sum/
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例:
给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]
相似题目
LeetCode.001.Two Sum 两数之和
LeetCode.653.Two Sum IV - Input is a BST 两数之和4-输入是BST
LeetCode.532.K-diff Pairs in an Array 数组中的k-diff数对
LeetCode.016.3Sum Closest 最接近的三数之和
LeetCode.015.3Sum 三数之和
18 四数之和
https://leetcode-cn.com/problems/4sum/
解题过程
看到这个题可能第一想法是固定一个变量,转化为 2 sum 问题,时间复杂度为 O(n^2)
,但难点是三元组判重。
比如全零数组 [0,0,0,0,0,0] ,要么进行特例判断,要么最后再进行判重。
排序+双指针
通过排序解决三元组判重问题,排序复杂度为 O(nlogn)
,不会增加最终的算法复杂度,因为至少也需要 O(n^2)
复杂度。
对于三元组 (a, b, c)
只要保证 a <= b <= c
,就能保证不重复。
这里的去重包括两方面,对于排序后的数组 nums[]
,需要:
1、每层循环 for(int i = 0; i < nums.length; i++)
要保证跳过重复元素,即 nums[i] != nums[i - 1]
2、内层循环的 nums[j]
要大于等于外层循环的 nums[i]
,这是为了不重复使用元素。
固定外层循环的 nums[i]
后,内两层循环的 nums[j]
和 nums[k]
是互相制约的关系,因为需要满足 nums[i] + nums[j] + nums[k] == 0
,所以 nums[j]
变大时 nums[k]
就必须变小。
利用这个制约关系,我们就可以通过 双指针 把内两层循环变为一层循环,将复杂度降低到 O(n)
左边界 left
从 i + 1
开始,右边界 right
从 nums.length - 1
开始
当 nums[i] + nums[left] + nums[right] < 0
时,只有左边界 left 右移才能增加 三数之和
当 nums[i] + nums[left] + nums[right] > 0
时,只有右边界 right 左移才能减少 三数之和
时间复杂度 O(n^2)
,其中排序复杂度为 O(nlogn)
空间复杂度 O(nlogn)
,排序需要这些空间复杂度
private static class SolutionV202006 {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
// 升序排序
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue; // 跳过重复元素
}
int left = i + 1;
int right = nums.length - 1;
while (left < nums.length && left < right) {
if (left > i + 1 && nums[left] == nums[left - 1]) {
left++;
continue; // 跳过重复元素
}
if (nums[i] + nums[left] + nums[right] == 0) {
res.add(Arrays.asList(nums[i], nums[left], nums[right]));
left++;
right--;
} else if (nums[i] + nums[left] + nums[right] < 0) {
// 三数之和比 0 小,左边界 left 右移
left++;
} else {
// 三数之和比 0 大,右边界 right 左移
right--;
}
}
}
return res;
}
}
GitHub代码
algorithms/leetcode/leetcode/_015_3Sum.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_015_3Sum.java
页面信息
location:
protocol
: host
: hostname
: origin
: pathname
: href
: document:
referrer
: navigator:
platform
: userAgent
: