解析

排序+双指针剪枝

三重循环肯定会超时，而且重复的部分解也不好处理。那么先对数组进行排序，在有序数组里跳过重复解的操作就简单多了，
三重循环显然可以改成二重循环，在第二层循环里值一不变，值二在增加，那么值三只能减少，把值三的指针从最大值开始往最小值方向遍历又可剪枝。

//! n^2, 1 -> 排序耗时是nlog(n),双重循环耗时是n^2;空间占用不算返回值的话且不计较修改了原数组的话是O(1)
class Solution {
 public:
  vector<vector<int>> threeSum(vector<int> &nums) {
    vector<vector<int>> res;
    sort(nums.begin(), nums.end());

    for (int i = 0; i < nums.size(); ++i) {
      int k = nums.size() - 1;  // k从最大值往最小值方向遍历
      if (i != 0 && nums[i - 1] == nums[i]) continue;
      for (int j = i + 1; j < nums.size(); j++) {
        if (j != i + 1 && nums[j - 1] == nums[j]) continue;
        while (j < k && nums[i] + nums[j] + nums[k] > 0) {
          --k;
        }
        if (j >= k) break;
        if (nums[i] + nums[j] + nums[k] == 0) {
          res.emplace_back(vector<int>{nums[i], nums[j], nums[k]});
          --k;
          continue;
        }
      }
    }

    return res;
  }
};

2025-02-02 该篇文章被 HopoZ 打上标签: leetcode 双指针排序归为分类: algo