15.三数之和

链接：15.三数之和
难度：Medium
标签：数组、双指针、排序
简介：给你一个包含 n 个整数的数组  nums，判断  nums  中是否存在三个元素 a，b，c ，使得  a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

题解 1 - typescript

• 编辑时间：2020-06-03
• 执行用时：148ms
• 内存消耗：46.1MB
• 编程语言：typescript
• 解法介绍：排序后将每个点作为中心位，增加左右指针。

function threeSum(nums: number[]): number[][] {
  const len = nums.length;
  if (len < 3) return [];
  const res = [];
  nums.sort((a, b) => a - b);
  for (let i = 0; i < len || nums[i] > 0; i++) {
    if (nums[i] == nums[i - 1]) continue; // 去重
    let L = i + 1;
    let R = len - 1;
    while (L < R) {
      const sum = nums[i] + nums[L] + nums[R];
      if (sum == 0) {
        res.push([nums[i], nums[L], nums[R]]);
        while (L < R && nums[L] == nums[L + 1]) L++; // 去重
        while (L < R && nums[R] == nums[R - 1]) R--; // 去重
        L++;
        R--;
      } else if (sum < 0) L++;
      else if (sum > 0) R--;
    }
  }
  return res;
}

题解 2 - typescript

• 编辑时间：2020-06-12
• 执行用时：144ms
• 内存消耗：45.9MB
• 编程语言：typescript
• 解法介绍：双指针判断。

function threeSum(nums: number[]): number[][] {
  const len = nums.length;
  nums = nums.sort((a, b) => a - b);
  const ans: number[][] = [];
  for (let i = 0; nums[i] <= 0; i++) {
    let l = i + 1;
    let r = len - 1;
    while (l < r) {
      const num = nums[i] + nums[l] + nums[r];
      if (num < 0) l++;
      else if (num > 0) r--;
      else {
        ans.push([nums[i], nums[l], nums[r]]);
        l++;
        while (nums[l] === nums[l - 1]) l++;
        r--;
        while (nums[r] === nums[r + 1]) r--;
      }
    }
    while (nums[i] === nums[i + 1]) i++;
  }
  return ans;
}

题解 3 - cpp

• 编辑时间：2022-02-18
• 执行用时：60ms
• 内存消耗：19.3MB
• 编程语言：cpp
• 解法介绍：循环双指针。

class Solution {
   public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size() && nums[i] <= 0; i++) {
            if (i != 0 && nums[i] == nums[i - 1]) continue;
            int sum, l = i + 1, r = nums.size() - 1;
            while (l < r) {
                sum = nums[l] + nums[r] + nums[i];
                if (sum == 0) {
                    ans.push_back(vector<int>{nums[i], nums[l], nums[r]});
                    while (l < r && nums[l] == nums[l + 1]) l++;
                    l++;
                } else if (sum > 0)
                    r--;
                else
                    l++;
            }
        }
        return ans;
    }
};

题解 4 - cpp

• 编辑时间：2023-07-09
• 执行用时：336ms
• 内存消耗：23.3MB
• 编程语言：cpp
• 解法介绍：二分。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        nums.push_back(INT_MAX);
        int n = nums.size();
        vector<vector<int>> res;
        int prev1 = INT_MIN;
        for (auto it1 = nums.begin(); it1 != nums.end() && *it1 <= 0; prev1 = *it1, it1++) {
            if (prev1 == *it1) continue;
            auto it2 = it1;
            it2++;
            int prev2 = INT_MIN;
            for (; it2 != nums.end(); prev2 = *it2, it2++) {
                if (prev2 == *it2) continue;
                int val = 0 - *it1 - *it2;
                if (val < *it2) continue;
                auto it3 = it2;
                it3++;
                it3 = lower_bound(it3, nums.end(), val);
                if (*it3 == val) {
                    res.push_back({ *it1, *it2, *it3 });
                }
            }
        }
        return res;
    }
};