三数之和

题面

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意： 答案中不可以包含重复的三元组

示例 1：

输入： nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入： nums = [0,1,1] 输出：[] 解释： 唯一可能的三元组和不为 0 。

示例 3：

输入： nums = [0,0,0] 输出：[[0,0,0]] 解释： 唯一可能的三元组和为 0 。

提示：

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

从两数之和出发

• 两数之和的做法是，遍历数组，通过哈希表查看其 target-num[i] 是否存在

• 这个题目也可以使用这种思想，使用两个循环遍历前两个数，然后通过哈希表查看其 -(a+b) 是否在数组中

• 这种做法有问题吗？例如对于数组 [-1,0,1,2,-1,-4]，当遍历到 -1、0 时，1 在数组中，然而当遍历到 0、-1 时，会导致两个元组重复

• 可以先对数组进行排序，在进行遍历时，如果下一个要遍历的元素与当前元素相同，就不能再进行遍历

• 代码实现

  #include <vector>
  #include <unordered_set>
  #include <set>
  #include <algorithm>
  using namespace std;
  
  class Solution {
  public:
      vector<vector<int>> threeSum(vector<int>& nums) {
          vector<vector<int>> result;
          int n = nums.size();
          if (n < 3) return result;
  
          sort(nums.begin(), nums.end());
  
          for (int i = 0; i < n - 2; ++i) {
              if (i > 0 && nums[i] == nums[i-1]) continue;
              if (nums[i] > 0) break;
  
              unordered_set<int> hash_set; // 存储已经遍历过的b，供查找c使用
              for (int j = i + 1; j < n; ++j) {
                  int target = -(nums[i] + nums[j]); // c需要满足的条件
  
                  if (hash_set.find(target) != hash_set.end()) {
                      result.push_back({nums[i], nums[j], target});
                      while (j < n-1 && nums[j] == nums[j+1]) ++j;
                  }
  
                  hash_set.insert(nums[j]);
              }
          }
  
          return result;
      }
  };

双指针

• 在对数组进行排序之后，在外层循环对每一个元素，可以使用双指针来确定另外两个数

• 两个指针相向移动，当前值小于 0，则移动左指针，否则移动右指针，当指针相遇则说明无法组成符合条件的元组

• 同样，也要避免外层重复遍历同一个元素

• 代码实现

  #include <vector>
  #include <algorithm>
  using namespace std;
  
  class Solution {
  public:
      vector<vector<int>> threeSum(vector<int>& nums) {
          vector<vector<int>> result;
          int n = nums.size();
          if (n < 3) {
              return result;
          }
  
          sort(nums.begin(), nums.end());
  
          for (int i = 0; i < n - 2; ++i) {
              if (nums[i] > 0) {
                  break;
              }
  
              if (i > 0 && nums[i] == nums[i - 1]) {
                  continue;
              }
  
              int left = i + 1;
              int right = n - 1;
              while (left < right) {
                  int sum = nums[i] + nums[left] + nums[right];
  
                  if (sum > 0) {
                      --right;
                  } else if (sum < 0) {
                      ++left;
                  } else {
                      result.push_back({nums[i], nums[left], nums[right]});
  
                      while (left < right && nums[left] == nums[left + 1]) {
                          ++left;
                      }
                      while (left < right && nums[right] == nums[right - 1]) {
                          --right;
                      }
  
                      ++left;
                      --right;
                  }
              }
          }
  
          return result;
      }
  };