《剑指 Offer》专项突破版 - 面试题 7 : 数组中和为 0 的 3 个数字（C++ 实现）

题目链接：15. 三数之和 - 力扣（LeetCode）

题目：

输入一个数组，如何找出数组中所有和为 0 的 3 个数字的三元组？需要注意的是，返回值中不得包含重复的三元组。例如，在数组 [-1, 0, 1, 2, -1, -4] 中有两个三元组的和为 0，它们分别是 [-1, 0, 1] 和 [-1, -1, 2]。

分析：

这个题目是题目 2.1 的加强版。如果输入的数组是排序的，就可以先固定一个数字 i，然后在排序数组中查找和为 -i 的两个数字。我们已经有了用 O(n) 时间在排序数组中找出和为给定值的两个数字的方法，由于需要固定数组中的每个数字，因此查找三元组的时间复杂度是 O(n^2)。

前面只需要 O(n) 时间在数组中找出和为给定值的两个数字的方法只适用于排序数组。可是这个题目并没有说给出的数组是排序的，因此需要先对数组排序。排序算法的时间复杂度通常是 O(nlogn)，因此这种解法的总的时间复杂度是 O(nlogn) + O(n^2)，仍然是 O(n^2)。

注意：为了避免出现重复的三元组，求解的过程中需要对 nums[i]、nums[j] 和 nums[k] 进行检查。

class Solution {
public:
 ? ?vector<vector<int>> threeSum(vector<int>& nums) {
 ? ? ? ?sort(nums.begin(), nums.end());
 ? ? ? ?vector<vector<int>> result;
 ? ? ? ?int n = nums.size();
 ? ? ? ?for (int i = 0; i < n - 2; ++i)
 ? ? ?  {
 ? ? ? ? ? ?if (i > 0 && nums[i] == nums[i - 1]) ?// 跳过重复的数字
 ? ? ? ? ? ? ? ?continue;
 ? ? ? ? ? ?
 ? ? ? ? ? ?int target = -nums[i];
 ? ? ? ? ? ?int left = i + 1;
 ? ? ? ? ? ?int right = n - 1;
 ? ? ? ? ? ?while (left < right)
 ? ? ? ? ?  {
 ? ? ? ? ? ? ? ?int sum = nums[left] + nums[right];
 ? ? ? ? ? ? ? ?if (sum < target)
 ? ? ? ? ? ? ? ? ? ?++left;
 ? ? ? ? ? ? ? ?else if (sum > target)
 ? ? ? ? ? ? ? ? ? ?--right;
 ? ? ? ? ? ? ? ?else
 ? ? ? ? ? ? ?  {
 ? ? ? ? ? ? ? ? ? ?result.push_back({ nums[i], nums[left], nums[right] });
 ? ? ? ? ? ? ? ? ? ?
 ? ? ? ? ? ? ? ? ? ?++left;
 ? ? ? ? ? ? ? ? ? ?while (left < right && nums[left] == nums[left - 1]) ?// 跳过重复的数字
 ? ? ? ? ? ? ? ? ? ? ? ?++left;
 ? ? ? ? ? ? ? ? ? ?
 ? ? ? ? ? ? ? ? ? ?--right;
 ? ? ? ? ? ? ? ? ? ?while (left < right && nums[right] == nums[right + 1]) ?// 跳过重复的数字
 ? ? ? ? ? ? ? ? ? ? ? ?--right;
 ? ? ? ? ? ? ?  }
 ? ? ? ? ?  }
 ? ? ?  }
 ? ? ? ?return result;
 ?  }
};