跳转至

LC15 - 三数之和

ThreeSum.go
 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
32
33
34
35
36
37
package DoublePointers

import "slices"

// 时间复杂度: O(n^2), 空间复杂度: O(1)
func threeSum(nums []int) [][]int {
    slices.Sort(nums)
    result := make([][]int, 0)
    for i := 0; i < len(nums)-2; i = next(i, nums) {
        j, k := i+1, len(nums)-1
        for j < k {
            if nums[i]+nums[j]+nums[k] == 0 {
                result = append(result, []int{nums[i], nums[j], nums[k]})
                j = next(j, nums)
                k = prev(k, nums)
            } else if nums[i]+nums[j]+nums[k] < 0 {
                j = next(j, nums)
            } else {
                k = prev(k, nums)
            }
        }
    }
    return result
}

func next(i int, nums []int) int {
    length := len(nums)
    for ; i+1 < length && nums[i] == nums[i+1]; i++ {
    }
    return i + 1
}

func prev(i int, nums []int) int {
    for ; i-1 >= 0 && nums[i] == nums[i-1]; i-- {
    }
    return i - 1
}

本题与LC1的最本质区别在于只需返回数值而不用原始数组的下标，因此非常适合使用双指针。

为了实现对结果的去重，需要实现next函数和prev函数以取代原本的--和++。