(刷题记录 6）三个数字之和
三数之和
- 题目信息：
- 题目思路(环境来自力扣OJ的C++)：
- 暴力枚举：
- 双指针：
- 在三数之和上：
- 转化成的两数之和：
- 两数之和小优化：
- 复杂度：
- 代码和解释：
- 暴力枚举：
- 双指针：
题目信息：
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
题目参考：力扣：15. 三数之和
题目思路(环境来自力扣OJ的C++)：
暴力枚举：
使用三层循环，先排序保证重复出现的三元组位置相同，之后依次遍历统计出三个数相加等于 0 的再放入 set 去重。
双指针：
在三数之和上：
-
先排序，方便移动去重与使用双指针。
-
因为排序相同的数是集中在一起的，可以判断将相同的数跳过。
-
使用第一层循环固定一个数，此时问题可以转化为 两数之和（nums[j] + nums[k] = - nums[i]）。
转化成的两数之和：
我们发现：
-
在升序排序状态下，下标向右移动，指向的元素一定会增大或不变，向左移动元素一定会减小或不变(单调性)，使用对撞指针可以利用这一特性。
-
如果两数之和大于 target (也就是 - nums[i])，要保证 和 的结果一定会减小或不变（为了接近 target），需要 右指针 向左移动，这时优化了没有必要的左指针向右移动。
-
如果两数之和小于 target，要保证 和 的结果一定会增大或不变，需要 左指针 向右移动，这时优化了没有必要的右指针向左移动。
-
对撞指针移动时，并不会出现回退的情况，也就是指针移动规则具有单调性，则双指针的使用有效。
-
由于题目要求去重，上述相同元素需要跳过。
-
注意，固定的 target 的下标 i 与之前也被固定的数不可以在对撞指针范围内，不然会出现重复元素，这里使用的是从大到小固定，则开始时 right = i - 1。
两数之和小优化：
- 当两个最大的数都小于 target，也就是 right = i - 1， arr[right] + arr[right - 1] < target 时，其他两个数的和一定会小于 target，可以直接退出。
- 当两个最小的数都大于 target，也就是 left = 0， arr[left] + arr[left + 1] > target 时，其他两个数的和一定会大于 target，可以直接退出。
复杂度：
暴力枚举：
时间复杂度：O(N ^ 3)
空间复杂度：O(logN)
双指针：
时间复杂度：O(N ^ 2)
空间复杂度：O(logN)
代码和解释：
暴力枚举：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) { // 暴力超时 O(N ^ 3)
sort(nums.begin(), nums.end()); // 排序
set<vector<int>> set; // 去重准备
for (int i = 0; i < nums.size() - 2; ++i) // 暴力枚举
{
for (int j = i + 1; j < nums.size() - 1; ++j)
{
for (int k = j + 1; k < nums.size(); ++k)
{
if (nums[i] + nums[j] + nums[k] == 0)
{
set.insert({nums[i], nums[j], nums[k]}); // 插入去重
}
}
}
}
vector<vector<int>> ans(set.begin(), set.end());
return ans; // 返回答案
}
};
双指针：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) { // 双指针 O(N ^ 2)
sort(nums.begin(), nums.end()); // 排序
vector<vector<int>> ans;
for (int i = nums.size() - 1; i >= 2; --i)
{
int target = -nums[i]; // 将三数之和转化为两数之和
int left = 0;
int right = i - 1;
bool flag = true;
if (nums[right] + nums[right - 1] < target
|| nums[left] + nums[left + 1] > target) // 小优化
{
flag = false;
}
while (flag && left < right) // 对撞指针 + 移动去重
{
if (nums[left] + nums[right] == target) // 相等存入答案
{
ans.push_back({nums[left++], nums[right--], nums[i]});
}
else if (nums[left] + nums[right] > target) // 大于时右指针移动反之左指针移动
{
--right;
}
else
{
++left;
}
while (left < right && left > 0 && nums[left] == nums[left - 1])
{
++left; // 左去重
}
while (left < right && right < i - 1 && nums[right] == nums[right + 1])
{
--right; // 右去重
}
}
while (i > 2 && nums[i] == nums[i - 1]) // 去重
{
--i;
}
}
return ans;
}
};