Day 26 - 15. 3sum
Day26 - 15.三数之和
LeetCode 15.三数之和
题目链接：
https://leetcode.cn/problems/3sum/
1. 题目描述
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意： 答案中不可以包含重复的三元组。
举个例子：
输入： 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. 思路解析
本题是经典的双指针类型的问题，解决此问题的核心在于以下两点。
左右指针的移动策略。
结果的去重策略。
例如：对于 a + b + c = 0
此时一层循环固定 a，此时问题变为 找出 b+ c == -a，就可以转化为双指针问题。
首先对数组nums进行升序排序，类似「167.两数之和II」，本次使用三个索引：i，left，right。初始值i = 0，left = i + 1，right = nums.size - 1。
算法如下：
nums[i] + nums[left] + nums[right] > target时，nums[left]或nums[right]需要一个更小的值，由于nums是升序的，故只能把索引right往左移，--right。如果left >= right，向右移动i，直到nums[i] != nums[i-1]（对nums[i]去重）。nums[i] + nums[left] + nums[right] < target时，nums[left]或nums[right]需要一个更大的值，由于nums是升序的，故只能把索引left往右移，++left。如果left >= right，向右移动i，直到nums[i] != nums[i-1]（对nums[i]去重）。nums[i] + nums[left] + nums[right] == target时，把当前三元组存到结果数组中，并且left右移直到nums[left-1] != nums [left](对nums[left]去重)去寻找下一个满足条件的三元组。如果left >= right，向右移动i，直到nums[i] != nums[i-1]（对nums[i]去重）。如果
i == nums.size()，算法结束。
3. C++代码
3.1. 暴力算法
老规矩，先上暴力！
暴力算法很容易想到，枚举三层变量...
关键是要处理好：
无重复三元组
边界条件
特殊情况（数组本来就不满三个...等等）
class Solution
{
public:
vector<vector<int>> threeSum(vector<int> &nums)
{
vector<vector<int>> res;
int nums_len = nums.size();
// 如果数组的元素少于三个，直接返回空
if (nums_len < 3)
{
return res;
}
// 先对数组进行排序，方便去重
// 快速排序 复杂度O(nlogn)
sort(nums.begin(), nums.end());
// 注意循环条件，由于 j,k 存在，i 不能达到 nums_len - 2
for (int i = 0; i < nums_len - 2; i++)
{
// 去除重复元素，如果重复，以最后一个为基准
if (i > 0 && nums[i] == nums[i - 1])
{
continue;
}
// 注意循环条件，从i + 1开始，不能达到 nums_len - 1
for (int j = i + 1; j < nums_len - 1; j++)
{
if (j > i + 1 && nums[j] == nums[j - 1])
{
continue;
}
for (int k = j + 1; k < nums_len; k++)
{
if (k > j + 1 && nums[k] == nums[k - 1])
{
continue;
}
// 此时判断找到的三元组是否符合条件
if ((nums[i] + nums[k] + nums[j]) == 0)
{
res.push_back({nums[i], nums[j], nums[k]});
}
}
}
}
return res;
}
};复杂度
，可预见的超时...
3.2. 双指针算法
class Solution
{
public:
vector<vector<int>> threeSum(vector<int> &nums)
{
vector<vector<int>> res;
int nums_len = nums.size();
// 正常排序方便去重
sort(nums.begin(), nums.end());
for (int i = 0; i < nums_len; i++)
{
int left = i + 1;
int right = nums_len - 1;
// 正常去重操作
if (i > 0 && nums[i - 1] == nums[i])
{
continue;
}
// 双指针大循环
while (left < right)
{
// 找到符合条件的三元组
if (nums[i] + nums[left] + nums[right] == 0)
{
// 添加进返回值
res.push_back({nums[i], nums[left], nums[right]});
// 左指针移动
left++;
// 左指针移动有可能出现重复值，所以也需要去重
// 注意去重条件
while (left < right && nums[left - 1] == nums[left])
{
left++;
}
}
// 小于 0，说明需要更大的值，根据之前排好序的数组，只能移动左指针
// 并且此时不用去重，因为就算重复，也只会继续循环，不会影响返回值，无非是多做几次循环
else if (nums[i] + nums[left] + nums[right] < 0)
{
left++;
}
// 大于 0，说明需要移动右指针
else if (nums[i] + nums[left] + nums[right] > 0)
{
right--;
}
}
}
return res;
}
};复杂度虽然没有很出色：
，但也够用。
关键是思路要打开，这个算法很好的把 三数之和 变为 两数之和，转化为双指针问题。
4. 复杂度分析
时间复杂度： 首先排序最快 O(nlogn)，然后索引i遍历一遍字符串nums，针对每个i，都有left和right共同遍历一遍nums，总共需要 O(n2)，故时间复杂度是 (nlogn) + O(n2) = O(n2)。
空间复杂度： 主要是排序消耗的空间，看具体的排序算法，快排的话是O(logn)，寻找三数之和的过程需要一个结果数组空间复杂度是O(n)，故总的空间复杂度是O(n)。
5. Redo. 02/04
双指针：左右指针收缩
预先排序：复杂度
去重操作：判断相邻元素是否相等
class Solution
{
public:
vector<vector<int>> threeSum(vector<int> &nums)
{
vector<vector<int>> res;
int nums_len = nums.size();
sort(nums.begin(), nums.end());
for(int a = 0; a < nums_len; a++)
{
if(a > 0 && nums[a] == nums[a - 1])
{
continue;
}
int left = a + 1;
int right = nums_len - 1;
while(left < right)
{
if(nums[a] + nums[left] + nums[right] == 0)
{
res.push_back({nums[a], nums[left], nums[right]});
left++;
while(left < right && nums[left - 1] == nums[left])
{
left++;
}
}
else if(nums[a] + nums[left] + nums[right] < 0)
{
left++;
}
else if(nums[a] + nums[left] + nums[right] > 0)
{
right--;
}
}
}
return res;
}
};Last updated