15-三数之和
@Author：CSU张扬
@Email：csuzhangyang@ or csuzhangyang@
1. 题目
给定一个包含n个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c，a，b，c ，a，b，c，使得 a+b+c=0a + b + c = 0a+b+c=0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组集合为：[[-1, 0, 1],[-1, -1, 2]]
来源：力扣（LeetCode）
链接：https://leetcode-/problems/3sum/
2. 解法
2.1 解法一：双指针法
首先对数组从大到小排序，数组的大小为n。固定一个数，从其右侧的数中寻找另外两个数。假设我们固定的数为nums[k], k = 0 to n-1, 另外两个数初始时分别为nums[l], nums[r], 其中l = k + 1, r = n - 1。令sum = nums[k] + nums[l] + nums[r]。 若sum < 0，则我们要增大sum，此时只能对l向右挪一格，即：l ++。若sum > 0，则我们要减小sum，此时只能对r向左挪一格，即：r --。若sum == 0，此时这三个数就我们需要的数，将他们加入结果里。此时，l和r之间的数还可能有我们需要的数，我们此时需要左右都向内移动，即：l ++, r --。。避免重复的数据。当sum == 0时，我们需要l和r都向内移动。此时需要过滤掉和当前nums[l], nums[r]重复的数据，我们巧妙的使用了两个while循环，同时需注意l 要一直小于 r。
while (l < r && nums[l] == nums[++ l]) { }
while (l < r && nums[r] == nums[-- r]) { }同时，我们也要在k的循环中过滤掉和当前nums[k]重复的数字。这里的k < len - 2主要是防止数组越界。
while (k < len - 2 && nums[k] == nums[++ k]) { }当l >= r时，说明与当前固定的nums[k]相组合的两个数已经找完，所以要进入下一个nums[k]。
执行用时: 112 ms, 在所有 cpp 提交中击败了98.73%的用户
内存消耗: 14.6 MB, 在所有 cpp 提交中击败了86.17%的用户
class Solution {public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> res;int len = nums.size();if (len < 3) {return res;}sort(nums.begin(), nums.end());int k = 0;while(k < len - 2 && nums[k] <= 0) {int l = k + 1;int r = len - 1;while (l < r) {int sum = nums[k] + nums[l] + nums[r];if (sum == 0) {res.push_back({nums[k], nums[l], nums[r]});while (l < r && nums[l] == nums[++ l]) {}while (l < r && nums[r] == nums[-- r]) {}}else if (sum < 0) {++ l;}else {-- r;}}while (k < len - 2 && nums[k] == nums[++ k]) {}}return res;}};
如果觉得《LeetCode(C++)刷题计划：15-三数之和》对你有帮助，请点赞、收藏，并留下你的观点哦！
