15. 三数之和

func threeSum(nums []int) [][]int {
    sort.Ints(nums)
    res := [][]int{}
    // 找出a + b + c = 0
    // a = nums[i], b = nums[left], c = nums[right]
    for i := 0; i < len(nums)-2; i++ {
        // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
        n1 := nums[i]
        if n1 > 0 {
            break
        }
        // 去重a
        if i > 0 && n1 == nums[i-1] {
            continue
        }
        l, r := i+1, len(nums)-1
        for l < r {
            n2, n3 := nums[l], nums[r]
            if n1+n2+n3 == 0 {
                res = append(res, []int{n1, n2, n3})
                // 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
                for l < r && nums[l] == n2 {
                    l++
                }
                for l < r && nums[r] == n3 {
                    r--
                }
            } else if n1+n2+n3 < 0 {
                l++
            } else {
                r--
            }
        }
    }
    return res
}

---

• 分类： 算法
• 标签： 算法基础 双指针