18.四数之和

排序+双指针，注意剪枝的几种情况。

1. 最小四个数比target大
2. 选择的前两个数遇到重复数字时
3. 剩下两数最大比 target-preSum 小或者最小比 target-preSum 大（也可以不判断）
4. 剩下两数遇到重复数字时

时间复杂度：O(n^3)
空间复杂度：O(logN)，快排的递归深度

func fourSum(nums []int, target int) [][]int {
    sort.Ints(nums)
    n := len(nums)
    ans := [][]int{}

    // 挑选第一个数
    for i := 0; i < n - 3; i++ {
        // 最小四个数比target还大，剪枝
        if nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target{
            continue
        }

        // 重复数字跳过
        if i > 0 && nums[i] == nums[i-1]{
            continue
        }

        // 挑选第二个数
        for j := i + 1; j < n - 2; j++{
            preSum := nums[i] + nums[j]

            // 重复数字跳过，从第i+2个数字开始
            if j > i + 1 && nums[j] == nums[j-1]{
                continue
            }

            // 剩下求两数之和
            l, r := j + 1, n - 1
            // 最大两数和比target小，剪枝
            if preSum + nums[r] + nums[r-1] < target{
                continue
            }
            // 最小两数和比target大，剪枝
            if preSum + nums[l] + nums[l+1] > target{
                continue
            }

            for l < r {
                if preSum + nums[l] + nums[r] == target {
                    ans = append(ans, []int{nums[i], nums[j], nums[l], nums[r]})
                    for l < r {
                        l++
                        // 当前数字和前一个数字不同则停止右移
                        if nums[l-1] != nums[l] {
                            break
                        }
                    }
                    for l < r  {
                        r--
                        // 当前数字和前一个数字不同则停止左移
                        if nums[r+1] != nums[j] {
                            break
                        }
                    }
                }
                if preSum + nums[l] + nums[r] < target{
                    l++
                }
                if preSum + nums[l] + nums[r] > target{
                    r--
                }
            }
        }
    }

    return ans
}