18. 四数之和

func fourSum(nums []int, target int) [][]int {
    var res [][]int
    for i, num1 := range nums {
        if len(nums) - i - 1 < 3 {
            return res
        }
        for j, num2 := range nums[i+1:] {
            if len(nums) - i - 1 - j - 1 < 2 {
                continue
            }
            for k, num3 := range nums[i+1+j+1:] {
                if len(nums) - i - 1 - j - 1 - k - 1 < 1 {
                    continue
                }
                for _, num4 := range nums[i+1+j+1+k+1:] {
                    if num1 + num2 + num3 + num4 == target {
                        res = append(res, []int{num1, num2, num3, num4})
                    }
                }
            }
        }
    }
    return res
}

import "sort"


func fourSum(nums []int, target int) [][]int {
    sort.Ints(nums)
    var res [][]int
    if len(nums) < 4 {
        return res
    }


    for i, num1 := range nums[:len(nums) - 3] {
        // 确保第一个数不重复
        if i > 0 && num1 == nums[i - 1] {
            continue
        }
        for j, num2 := range nums[i+1:len(nums)-2] {
            // 确保第二个数不重复
            if j > 0 && num2 == nums[i+1+j-1] {
                continue
            }


            x := i+1+j+1
            y := len(nums)-1


            for x < y {
                if num1 + num2 + nums[x] + nums[y] < target {
                    x++
                } else if num1 + num2 + nums[x] + nums[y] > target {
                    y--
                } else {
                    res = append(res, []int{num1, num2, nums[x], nums[y]})


                    for x < y && nums[x+1] == nums[x] {
                        // 确保第三个数不重复
                        x++
                    }
                    for x < y && nums[y-1] == nums[y] {
                        // 确保第四个数不重复
                        y--
                    }
                    // 开始计算下个不同的第三个数和第四个数
                    x++
                    y--
                }
            }
        }
    }


    return res
}