题目

给定一个数组 nums 和目标数 target。找到四个数字使得这四个数相加等于目标数。

解析

和三数相加一样，先排序，固定两个数字，然后左右指针移动三个两个数字，去重方法也相同。

左右指针移动时，判断重复
移动固定指针时，步进到下一个不同的数字。

所以这是一个 n3 的时间复杂度。

伪代码

for i：=0; i< len-3; i++
    for j := i+1; j<len-2; j++
        h := j+1
        t := len-1
        for  h<t
          if sum == target
            if valid 
              rst=append(sum)
             h++,t--
          if sum < target
             h++
          if sum > target
             t--
      for nums[j]==nums[j+1]
          j++

    for nums[i] == nums[i+1]
        i++
    return rst

代码

func fourSum(nums []int, target int) [][]int {
    sort.Ints(nums)
    var rst [][]int
    for i:=0; i<len(nums)-3; i++ {
        for j:=i+1; j<len(nums)-2; j++ {
            h:=j+1
            t:=len(nums)-1
            for ; h<t; {
                sum := nums[i] + nums[j] + nums[h] + nums[t]
                if sum==target{
                    if h==j+1 || t==len(nums)-1 || nums[h] != nums[h-1] || nums[t] != nums[t+1] {
                        rst = append(rst, []int{nums[i], nums[j], nums[h], nums[t]})
                    } 
                    h++
                    t--
                }
                if sum < target {
                    h++
                }
                if sum > target {
                    t--
                }
            }
            for j<len(nums)-2 && nums[j] == nums[j+1] {
                j++
            }
        }
        for i < len(nums)-3 && nums[i] == nums[i+1] {
            i++
        }
    }
    return rst
}