跳转至

15. 三数之和

题目

给你一个整数数组 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 。

题解

Go
func threeSum(nums []int) (ans [][]int) {
    slices.Sort(nums)
    n := len(nums)
    for i, x := range nums[:n-2] {
        if i > 0 && x == nums[i-1] { // 跳过重复数字
            continue
        }
        if x+nums[i+1]+nums[i+2] > 0 { // 优化一
            break
        }
        if x+nums[n-2]+nums[n-1] < 0 { // 优化二
            continue
        }
        j, k := i+1, n-1
        for j < k {
            s := x + nums[j] + nums[k]
            if s > 0 {
                k--
            } else if s < 0 {
                j++
            } else {
                ans = append(ans, []int{x, nums[j], nums[k]})
                for j++; j < k && nums[j] == nums[j-1]; j++ {} // 跳过重复数字
                for k--; k > j && nums[k] == nums[k+1]; k-- {} // 跳过重复数字
            }
        }
    }
    return
}
Python
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        ans = []
        n = len(nums)
        for i in range(n - 2):
            x = nums[i]
            if i > 0 and x == nums[i - 1]:  # 跳过重复数字
                continue
            if x + nums[i + 1] + nums[i + 2] > 0:  # 优化一
                break
            if x + nums[-2] + nums[-1] < 0:  # 优化二
                continue
            j = i + 1
            k = n - 1
            while j < k:
                s = x + nums[j] + nums[k]
                if s > 0:
                    k -= 1
                elif s < 0:
                    j += 1
                else:
                    ans.append([x, nums[j], nums[k]])
                    j += 1
                    while j < k and nums[j] == nums[j - 1]:  # 跳过重复数字
                        j += 1
                    k -= 1
                    while k > j and nums[k] == nums[k + 1]:  # 跳过重复数字
                        k -= 1
        return ans
Python
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res, k = [], 0
        # 固定k
        for k in range(len(nums) - 2):
            # 1. because of j > i > k.
            if nums[k] > 0: 
                break 
            # 2. skip the same `nums[k]`.
            if k > 0 and nums[k] == nums[k - 1]: 
                continue 
            i, j = k + 1, len(nums) - 1
            # 3. double pointer
            while i < j: 
                s = nums[k] + nums[i] + nums[j]
                if s < 0:
                    i += 1
                    while i < j and nums[i] == nums[i - 1]:
                        i += 1
                elif s > 0:
                    j -= 1
                    while i < j and nums[j] == nums[j + 1]:
                        j -= 1
                else:
                    res.append([nums[k], nums[i], nums[j]])
                    i += 1
                    j -= 1
                    while i < j and nums[i] == nums[i - 1]:
                        i += 1
                    while i < j and nums[j] == nums[j + 1]:
                        j -= 1
        return res

复杂度

  • 时间复杂度: \(O(n^2)\)，其中 \(n\) 是 \(nums\) 的长度。排序\(O(n \ logn)\)，双指针操作\(O(n^2)\)。总的时间复杂度为\(O(n^2)\)。
  • 空间复杂度: \(O(1)\)。

参考