【LeetCode通关全记录】15. 三数之和

题目地址：15. 三数之和

解法：排序+双指针

这道题最简单的解法当然是暴力：三个嵌套的for循环，但是估计多半会TLE，而且一直暴力也不是很好的选择，所以可以使用一种更高效的解法：排序+双指针。

首先对输入的数组进行排序，然后从头开始遍历数组中的每一个负数。设当前遍历到的负数的下标为i，那么使用两个指针l和r分别指向nums[i+1]和nums[len(nums)-1]。接着进行判断：

1. 如果nums[i] + nums[l] + nums[r] == 0，说明找到了一组解，放入结果集合中，并将l右移一位，r左移一位；
2. 如果和大于0，将r左移一位；
3. 如果和小于0，将l右移一位；
4. 直到l >= r时退出循环，把i右移一位，继续判断下一组数。

这道题的难点在于去重的情况的判断，有两个地方需要去重：

1. 当i不是0时，需要判断nums[i]和nums[i+1]是否相等，如果相等，那么跳过这个数；
2. 当找到了一组解之后，在移动l和r之前，需要判断nums[l]是否等于numsa[l+1]、nums[r]是否等于nums[r-1]，如果是，则跳过相应的数。

这时我们也能明白为什么只需要考虑数组中的负数了：若nums[i] > 0，由于数组是经过排序的，那么nums[l]和nums[r]必然都大于0，相加之后也必然大于0。

func threeSum(nums []int) [][]int {
    if nums == nil || len(nums) < 3 {
        return [][]int{}
    }
    sort.Ints(nums)
    ans := [][]int{}
    for i := 0; i < len(nums); i++ {
        if nums[i] > 0 {
            // 正数，说明后面的数都是正数了不会出现和等于0的情况，跳出循环
            break
        }
        if i > 0 && nums[i-1] == nums[i] {
            // 去一下重
            continue
        }
        l, r := i+1, len(nums)-1
        for l < r {
            sum := nums[i] + nums[l] + nums[r]
            if sum == 0 {
                ans = append(ans, []int{nums[i], nums[l], nums[r]})
                // 去重。。。
                for l < r && nums[l] == nums[l+1] {
                    l++
                }
                // 继续去重。。。
                for l < r && nums[r] == nums[r-1] {
                    r--
                }
                // 判断下一对数
                l++
                r--
            } else if sum > 0 {
                r--
            } else { // sum < 0
                l++
            }
        }
    }
    return ans
}

执行用时：20 ms, 在所有 Go 提交中击败了99.93%的用户；

内存消耗：7.4 MB, 在所有 Go 提交中击败了90.06%的用户；

时间复杂度：O(n ^2)，有两层嵌套的for循环；

空间复杂度：O(logn)，来自排序算法，注意我们不需要考虑返回值所占的空间。