15. 三数之和(双指针)

15. 三数之和

给你一个包含 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]]

示例 2：

输入：nums = []
输出：[]

示例 3：

输入：nums = [0]
输出：[]

提示：

• 0 <= nums.length <= 3000
• -105 <= nums[i] <= 105

 1 class Solution {
 2 public:
 3     vectorint>> twoSum(vector<int> &nums, int start, int end, int target, int value) {
 4         vectorint>> ans;
 5         while (start < end) {
 6             int sum = nums[start] + nums[end];
 7             if (target == sum) {
 8                 vector<int> result;
 9                 result.emplace_back(value);
10                 result.emplace_back(nums[start]);
11                 result.emplace_back(nums[end]);
12                 ans.emplace_back(result);
13                 // 继续查找下一组
14                 while (start < end && nums[start] == nums[start + 1]) {
15                     start++;
16                 }
17                 start++;
18                 while (start < end && nums[end] == nums[end - 1]) {
19                     end--;
20                 }
21                 end--;
22             } else if (sum < target) { // 两数之和小于目标值,增加两数之和
23                 start++;
24             } else { // 两数之和大于目标值,减小两数之和
25                 end--;
26             }
27         }
28         return ans;
29     }
30     vectorint>> threeSum(vector<int>& nums) {
31         vectorint>> ans;
32         if (nums.size() < 3) {
33             return ans;
34         }
35         int size = nums.size();
36         sort(nums.begin(), nums.end());
37         for (int i = 0; i < size; i++) {
38             if (i > 0 && (nums[i] == nums[i - 1])) { // 消除重复解
39                 continue;
40             }
41             // 从nums数组起始i+1位置到结尾size-1位置,查找是否存在目标值(-nums[i]),满足两数之和为-nums[i]
42             auto result = twoSum(nums, i + 1, size - 1, -nums[i], nums[i]);
43             ans.insert(ans.end(), result.begin(), result.end());
44         }
45         return ans;
46     }
47 };