go_leetcode/018_4Sum.go at master · supercym/go_leetcode · GitHub

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
func fourSum(nums []int, target int) [][]int {
    sort.Ints(nums)
    length := len(nums)
    ans := make([][]int, 0)
    for i := 0; i < length; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        for j := i+1; j < length; j++ {
            if j > i+1 && nums[j] == nums[j-1] {
                continue
            }
            l, r := j+1, length-1
            for l < r {
                s := nums[l]+nums[r]
                if s < target-nums[i]-nums[j] {
                    l++
                } else if s > target-nums[i]-nums[j] {
                    r--
                } else {
                    if l > j+1 && nums[l] == nums[l-1] {
                        l, r = l+1, r-1
                    } else {
                        ans = append(ans, []int{nums[i], nums[j], nums[l], nums[r]})
                        l, r = l+1, r-1
                    }
                }
            }
        }
    }
    return ans
}