Three Sum

15. 三数之和

算法

排序数组：
- 首先将数组从小到大排序，方便后续操作
固定一个数，双指针搜索：
- 遍历排序后的数组，用 i 指向当前固定的数
- 在 i 的右侧，使用双指针 j 和 k：
  - j 指向 i + 1
  - k 指向数组末尾
- 检查三数之和：
  - 若三数之和小于 0，说明需要更大的值，移动 j 向右
  - 若三数之和大于 0，说明需要更小的值，移动 k 向左
  - 若三数之和等于 0，记录结果，同时移动 j 和 k 跳过重复值
去重：
- 对于固定数 nums[i]，若 nums[i] = nums[i-1]，跳过当前遍历，避免重复三元组
- 对于 nums[j] 和 nums[k]，在找到一个解后，继续移动跳过相同值

复杂度分析

时间复杂度

排序复杂度：O(nlogn)
三重循环复杂度：外层循环 O(n)，内层双指针 O(n)，总复杂度为 O(n^2)
总时间复杂度 O(n^2)

空间复杂度

使用排序 O(logn) 的额外空间，其余操作在原地完成，空间复杂度为 O(1)

C++ 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


class Solution
{
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        std::vector<std::vector<int>> res;
        std::sort(nums.begin(), nums.end()); // 对数组进行排序

        for (int i = 0; i < nums.size(); ++i)
        {
            // 跳过重复的固定数
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            // 双指针寻找其他两数
            for (int j = i + 1, k = nums.size() - 1; j < k; ++ j)
            {
                // 跳过重复的第二个数
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;

                // 移动右指针，寻找满足条件的三元组
                while (j < k - 1 && nums[i] + nums[j] + nums[k - 1] >= 0) -- k;

                // 判断当前三数之和是否为零
                if (nums[i] + nums[j] + nums[k] == 0)
                    res.push_back({nums[i], nums[j], nums[k]});
            }
        }

        return res;
    }
};

Python 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution:
  def threeSum(self, nums: List[int]) -> List[List[int]]:
    res = []
    nums.sort()
    for i in range(len(nums)):
      if i > 0 and nums[i] == nums[i - 1]:
        continue
      j, k = i + 1, len(nums) - 1
      while j < k:
        if j > i + 1 and nums[j] == nums[j - 1]:
          j += 1
          continue
        while j < k - 1 and nums[i] + nums[j] + nums[k - 1] >= 0:
          k -= 1
        if nums[i] + nums[j] + nums[k] == 0:
          res.append([nums[i], nums[j], nums[k]])
        j += 1
    return res

Go 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


func threeSum(nums []int) [][]int {
  res := [][]int{}
  sort.Ints(nums)
  for i := 0; i < len(nums); i ++ {
    if i > 0 && nums[i] == nums[i - 1] {
      continue
    }
    for j, k := i + 1, len(nums) - 1; j < k; j ++ {
      if j > i + 1 && nums[j] == nums[j - 1] {
        continue
      }
      for j < k - 1 && nums[i] + nums[j] + nums[k - 1] >= 0 {
        k --
      }
      if nums[i] + nums[j] + nums[k] == 0 {
        res = append(res, []int{nums[i], nums[j], nums[k]})
      }
    }
  }
  return res
}

JavaScript 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  let res = [];
  nums.sort((a, b) => a - b);

  for (let i = 0; i < nums.length; i++) {
    if (i > 0 && nums[i] == nums[i - 1]) {
      continue;
    }
    for (let j = i + 1, k = nums.length - 1; j < k; j++) {
      if (j > i + 1 && nums[j] == nums[j - 1]) {
        continue;
      }
      while (j < k - 1 && nums[i] + nums[j] + nums[k - 1] >= 0) {
        k--;
      }
      if (nums[i] + nums[j] + nums[k] == 0) {
        res.push([nums[i], nums[j], nums[k]]);
      }
    }
  }
  return res;
};