双指针——三数之和
一.题目描述
二.题目解析
题目还是很好理解的，就是找到三个数和为0即可。但是题目中的注意事项：不可以包含重复的三元组的描述很模糊，怎么才算重复呢？是完全相等，还是只要包含相同元素就行呢？
我们可以根据示例1来得出结论：和为0的三元组有->[-1、0、1]，[0、1、-1]，[-1、-1、2]。但是结果只有两种，所以我们得出结论，只要三元组的包含相同元素就算重复。
三.算法原理
1.暴力枚举
我们可以枚举出所有可能的三元组，然后判断其和是否为0即可。但是如果直接暴力枚举的话，就有可能出现三元组中数据相同，但顺序不同的结果。此时我们不好判断三元组是否相等。
所以我们可以先对数据进行排序，这样得出的三元组很容易判断是否相等。
接下来，因为有可能有多组相同的三元组，所以我们还需要去重操作，这里我们直接借助容器unordered_set来实现去重即可。
所以暴力算法的整体逻辑就是：排序+暴力枚举+unordered_set去重。
时间复杂度：因为要依次固定每一个数，所以要三层循环，时间复杂度为O(N^3)。
2.排序+双指针
我们先对数据进行排序，然后利用单调性+双指针的方式来解决问题。
我们排完序之后，先选择一个数a，然后在剩下的区间中选择两个数和为-a即可。其实这就回到了前一道题，和为s的两个数。
处理细节问题：
避免遗漏：当我们在left~right区间内找到了第一个和为-a的数之后，不应该返回，而是继续查找，因为该区间内可能还有其他和为-a的二元组。
去重：在暴力枚举中我们采用了容器去重的方式，但是还可以进行优化。当在left~right区间内找到了和为-a的二元组之后，left++，right--,如果该位置的值与之前的值相同，那就没必要在判断了，直接从下一个不相等的位置开始查找。期间需要避免越界访问。
同时选取a也要避免重复选择相同的值，遍历完一个值后，从下一个不相等的值再开始找，当然也要避免越界。
选a的小优化：因为数据是递增的，且left永远再a的下一个位置。所以当a>0之后，left、right位置的数和永远为正数，三个正数和不可能为0，所以a应该<=0，不必将所有的值都选一次做a。
综上：该算法的时间复杂度为:O(N^2)。
四.代码实现
这里的插入操作用到了initialize_list，通过隐式类型转换为vector<int>。
vector<vector<int>> vv;
// 1.排序
sort(nums.begin(), nums.end());
// 2.固定一个数 a,并求其相反数target
int i = 0;
while (i < nums.size())
{
int a = nums[i];
int target = a * -1;
//当a为大于0的数时，剩下的区间都是正数，加起来不可能为0，直接break
if (a > 0)
{
break;
}
//区间查找和为target的二元组
int left = i + 1;
int right = nums.size() - 1;
while (left < right)
{
if (nums[left] + nums[right] > target)
{
right--;
}
else if (nums[left] + nums[right] < target)
{
left++;
}
else
{
//插入三元组
vv.push_back({ nums[i],nums[left],nums[right] });
//继续在该区间查找，同时跳过相同的元素
int lprev = left++;
int rprev = right--;
while (left < right && nums[left] == nums[lprev])
{
++left;
}
while (left < right && nums[right] == nums[rprev])
{
right--;
}
}
}
//对a进行去重操作
++i;
while (i < nums.size() && nums[i] == a)
{
++i;
}
}
return vv;原文地址：https://blog.csdn.net/xsc2004zyj/article/details/144784942
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！