13_中等_三数之和

13 三数之和

https://leetcode.cn/problems/3sum/

算法：时间复杂度O(n2)

1-先对数组进行升序排序，然后逐一遍历，固定当前元素nums[i]，使用左右指针遍历当前元素后面的所有元素，nums[l]和nums[r]，如果三数之和=0，则添加进结果集

2-当nums[i] > 0 结束循环 // 升序排序，三数之和必然大于零

3-当nums[i] == nums[i-1] 表明用重复元素，跳过

4-sum = 0时, 如果nums[l] == nums[l+1] 重复元素，跳过

5-sum = 0时, nums[r] == nums[r-1] 重复元素，跳过

// date 2020/03/29
func threeSum(nums []int) [][]int {
    sort.Slice(nums, func(i, j int) bool {
        return nums[i] < nums[j]
    })
    res, n, sum := make([][]int, 0), len(nums), -1
    left, right := 0, n-1
    for i := 0; i < n; i++ {
        // 升序排列，大于零则退出
        if nums[i] > 0 { break }
        // 去重
        if i > 0 && nums[i] == nums[i-1] { continue }
        left, right = i+1, n-1
        for left < right {
            sum = nums[i] + nums[left] + nums[right]
            if sum < 0 {
                left++
            } else if sum > 0 {
                right--
            } else if sum == 0 {
                res = append(res, []int{nums[i], nums[left], nums[right]})
                // 去重
                for left < right && nums[left] == nums[left+1] { left++ }
                for left < right && nums[right] == nums[right-1] { right-- }
                left++
                right--
            }
        }
    }
    return res
}