[Leetcode] 15. 3Sum

 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

func threeSum(nums []int) [][]int {
    var result [][]int
    sort.Ints(nums)

    for i := 0; i < len(nums) - 2; i++ {
        left := i + 1
        right := len(nums) - 1
        
        for left < right {
            sum := nums[i] + nums[left] + nums[right]
            if sum < 0 {
                left += 1
            } else if sum > 0 {
                right -= 1
            } else {
                result = append(result, []int{nums[i], nums[left], nums[right]})

                for left < right && nums[left] == nums[left + 1] {
                    left += 1
                }

                for left < right && nums[right] == nums[right - 1] {
                    right -= 1
                }

                left += 1
                right -= 1
            }
        }
        for i + 1 < len(nums) && nums[i+1] == nums[i] {
            i += 1
        }
    }


    return result
}