LeetCode 18 四数之和

题目：

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n

a、b、c 和 d 互不相同

nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

解题：

循环处理，这次多了一个，应该不是双指针了吧

代码：

func fourSum(nums []int, target int) [][]int {
    l := len(nums)
    if l < 4 {
        return [][]int{}
    }
    var res [][]int
    sort.Ints(nums)
    for i := 0; i < l-3; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        for j := i + 1; j < l-2; j++ {
            if j > i+1 && nums[j] == nums[j-1] {
                continue
            }
            for k := j + 1; k < l-1; k++ {
                if k > j+1 && nums[k] == nums[k-1] {
                    continue
                }
                for m := k + 1; m < l; m++ {
                    if m > k+1 && nums[m] == nums[m-1] {
                        continue
                    }
                    if nums[i]+nums[j]+nums[k]+nums[m] == target {
                        res = append(res, []int{nums[i], nums[j], nums[k], nums[m]})
                    }
                }
            }
        }
    }
    return res
}

官方解答：排序+双指针

func fourSum(nums []int, target int) [][]int {
    sort.Ints(nums)
    n := len(nums)
    var res [][]int
    for i := 0; i < n-3 && nums[i]+nums[i+1]+nums[i+2]+nums[i+3] <= target; i++ {
        if i > 0 && nums[i] == nums[i-1] || nums[i]+nums[n-1]+nums[n-2]+nums[n-3] < target {
            continue
        }
        for j := i + 1; j < n-2 && nums[i]+nums[j]+nums[j+1]+nums[j+2] <= target; j++ {
            if j > i+1 && nums[j] == nums[j-1] || nums[i]+nums[j]+nums[n-1]+nums[n-2] < target {
                continue
            }
            left, right := j+1, n-1
            for left < right {
                if sum := nums[i] + nums[j] + nums[left] + nums[right]; sum == target {
                    res = append(res, []int{nums[i], nums[j], nums[left], nums[right]})
                    for left++; left < right && nums[left] == nums[left-1]; left++ {
                    }
                    for right--; left < right && nums[right] == nums[right+1]; right-- {
                    }
                } else if sum < target {
                    left++
                } else {
                    right--
                }
            }
        }
    }
    return res
}

排序，然后先循环一次最外面的一层，再双指针，又是没有掌握双指针的一天。。。