【数据结构与算法】之深入解析“三数之和”的求解思路与算法示例
【摘要】
一、题目要求
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。注意:答案中不可以包...
一、题目要求
- 给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。
- 注意:答案中不可以包含重复的三元组。
- 示例 1:
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
- 1
- 2
- 示例 2:
输入:nums = []
输出:[]
- 1
- 2
- 示例 3:
输入:nums = [0]
输出:[]
- 1
- 2
- 提示:
-
- 0 <= nums.length <= 3000;
-
- -105 <= nums[i] <= 105。
二、求解算法
① 快速排序
- 先将数组进行排序;
- 从左侧开始,选定一个值为定值 ,右侧进行求解,获取与其相加为 0 的两个值;
- 类似于快排,定义首和尾;
- 首尾与定值相加:
-
- 等于 0,记录这三个值;
-
- 小于 0,首部右移;
-
- 大于 0,尾部左移;
- 定值右移,重复该步骤。
- Java 示例:
var threeSum = function(nums) {
// 最左侧值为定值,右侧所有值进行两边推进计算
let res = [];
nums.sort((a, b) => a - b);
let size = nums.length;
if (nums[0] <= 0 && nums[size - 1] >= 0) {
// 保证有正数负数
let i = 0;
while (i < size - 2) {
if (nums[i] > 0) break; // 最左侧大于0,无解
let first = i + 1;
let last = size - 1;
while (first < last) {
if (nums[i] * nums[last] > 0) break; // 三数同符号,无解
let sum = nums[i] + nums[first] + nums[last];
if (sum === 0) {
res.push([nums[i], nums[first], nums[last]]);
}
if (sum <= 0) {
// 负数过小,first右移
while (nums[first] === nums[++first]) {} // 重复值跳过
} else {
while (nums[last] === nums[--last]) {} // 重复值跳过
}
}
while (nums[i] === nums[++i]) {}
}
}
return res;
};
- 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
② 排序 + 双指针
- 题目中要求找到所有「不重复」且和为 0 的三元组,这个「不重复」的要求使得无法简单地使用三重循环枚举所有的三元组。这是因为在最坏的情况下,数组中的元素全部为 0,即:
[0, 0, 0, 0, 0, ..., 0, 0, 0]
- 1
- 任意一个三元组的和都为 0,如果直接使用三重循环枚举三元组,会得到 O(N3) 个满足题目要求的三元组(其中 N 是数组的长度)时间复杂度至少为 O(N3)。在这之后,还需要使用哈希表进行去重操作,得到不包含重复三元组的最终答案,又消耗了大量的空间。这个做法的时间复杂度和空间复杂度都很高,因此要换一种思路来考虑这个问题。
- 「不重复」的本质是什么?我们保持三重循环的大框架不变,只需要保证:
-
- 第二重循环枚举到的元素不小于当前第一重循环枚举到的元素;
-
- 第三重循环枚举到的元素不小于当前第二重循环枚举到的元素。
- 也就是说,枚举的三元组 (a,b,c) 满足 a≤b≤c,保证了只有 (a,b,c) 这个顺序会被枚举到,而 (b,a,c)、(c,b,a) 等这些不会,这样就减少了重复。要实现这一点,可以将数组中的元素从小到大进行排序,随后使用普通的三重循环就可以满足上面的要求。
- 同时,对于每一重循环而言,相邻两次枚举的元素不能相同,否则也会造成重复。举个例子,如果排完序的数组为:
[0, 1, 2, 2, 2, 3]
^ ^ ^
- 1
- 2
- 使用三重循环枚举到的第一个三元组为 (0,1,2),如果第三重循环继续枚举下一个元素,那么仍然是三元组 (0,1,2),产生了重复。因此需要将第三重循环「跳到」下一个不相同的元素,即数组中的最后一个元素 3,枚举三元组 (0,1,3)。
- 下面给出了改进的方法的伪代码实现:
nums.sort()
for first = 0 .. n-1
// 只有和上一次枚举的元素不相同,才会进行枚举
if first == 0 or nums[first] != nums[first-1] then
for second = first+1 .. n-1
if second == first+1 or nums[second] != nums[second-1] then
for third = second+1 .. n-1
if third == second+1 or nums[third] != nums[third-1] then
// 判断是否有 a+b+c==0
check(first, second, third)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 这种方法的时间复杂度仍然为 O(N3),毕竟还是没有跳出三重循环的大框架。然而它是很容易继续优化的,可以发现,如果我们固定了前两重循环枚举到的元素 a 和 b,那么只有唯一的 c 满足 a+b+c=0。当第二重循环往后枚举一个元素 b′ 时,由于 b′ >b,那么满足 a + b′ +c′ = 0 的 c′ 一定有 c′ < c,即 c′ 在数组中一定出现在 c 的左侧。也就是说,可以从小到大枚举 b,同时从大到小枚举 c,即第二重循环和第三重循环实际上是并列的关系。
- 有了这样的发现,就可以保持第二重循环不变,而将第三重循环变成一个从数组最右端开始向左移动的指针,从而得到下面的伪代码:
nums.sort()
for first = 0 .. n-1
if first == 0 or nums[first] != nums[first-1] then
// 第三重循环对应的指针
third = n-1
for second = first+1 .. n-1
if second == first+1 or nums[second] != nums[second-1] then
// 向左移动指针,直到 a+b+c 不大于 0
while nums[first]+nums[second]+nums[third] > 0
third = third-1
// 判断是否有 a+b+c==0
check(first, second, third)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 这个方法就是常说的「双指针」,当我们需要枚举数组中的两个元素时,如果发现随着第一个元素的递增,第二个元素是递减的,那么就可以使用双指针的方法,将枚举的时间复杂度从 O(N2) 减少至 O(N)。为什么是 O(N)呢?这是因为在枚举的过程每一步中,「左指针」会向右移动一个位置(也就是题目中的 b),而「右指针」会向左移动若干个位置,这个与数组的元素有关,但我们知道它一共会移动的位置数为 O(N),均摊下来,每次也向左移动一个位置,因此时间复杂度为 O(N)。
- 注意到我们的伪代码中还有第一重循环,时间复杂度为 O(N),因此枚举的总时间复杂度为 O(N2)。由于排序的时间复杂度为 O(N logN),在渐进意义下小于前者,因此算法的总时间复杂度为 O(N2)。
- C++ 示例:
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
// 枚举 a
for (int first = 0; first < n; ++first) {
// 需要和上一次枚举的数不相同
if (first > 0 && nums[first] == nums[first - 1]) {
continue;
}
// c 对应的指针初始指向数组的最右端
int third = n - 1;
int target = -nums[first];
// 枚举 b
for (int second = first + 1; second < n; ++second) {
// 需要和上一次枚举的数不相同
if (second > first + 1 && nums[second] == nums[second - 1]) {
continue;
}
// 需要保证 b 的指针在 c 的指针的左侧
while (second < third && nums[second] + nums[third] > target) {
--third;
}
// 如果指针重合,随着 b 后续的增加
// 就不会有满足 a+b+c=0 并且 b<c 的 c 了,可以退出循环
if (second == third) {
break;
}
if (nums[second] + nums[third] == target) {
ans.push_back({nums[first], nums[second], nums[third]});
}
}
}
return ans;
}
};
- 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
- 36
- 37
- 38
- Java 示例:
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<List<Integer>>();
// 枚举 a
for (int first = 0; first < n; ++first) {
// 需要和上一次枚举的数不相同
if (first > 0 && nums[first] == nums[first - 1]) {
continue;
}
// c 对应的指针初始指向数组的最右端
int third = n - 1;
int target = -nums[first];
// 枚举 b
for (int second = first + 1; second < n; ++second) {
// 需要和上一次枚举的数不相同
if (second > first + 1 && nums[second] == nums[second - 1]) {
continue;
}
// 需要保证 b 的指针在 c 的指针的左侧
while (second < third && nums[second] + nums[third] > target) {
--third;
}
// 如果指针重合,随着 b 后续的增加
// 就不会有满足 a+b+c=0 并且 b<c 的 c 了,可以退出循环
if (second == third) {
break;
}
if (nums[second] + nums[third] == target) {
List<Integer> list = new ArrayList<Integer>();
list.add(nums[first]);
list.add(nums[second]);
list.add(nums[third]);
ans.add(list);
}
}
}
return ans;
}
}
- 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
- 36
- 37
- 38
- 39
- 40
- 41
- 复杂度分析:
-
- 时间复杂度:O(N2),其中 N 是数组 nums 的长度。
-
- 空间复杂度:O(logN)。忽略存储答案的空间,额外的排序的空间复杂度为 O(logN)。然而修改了输入的数组 nums,在实际情况下不一定允许,因此也可以看成使用了一个额外的数组存储了 nums 的副本并进行排序,空间复杂度为 O(N)。
文章来源: blog.csdn.net,作者:Serendipity·y,版权归原作者所有,如需转载,请联系作者。
原文链接:blog.csdn.net/Forever_wj/article/details/122500748
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)