18. 四数之和

算法原链接

https://leetcode-cn.com/problems/4sum/

解题思路

四数之和的解题思路可以类比三数之和，依靠双指针解法进行求解，但是双指针的解法的前提是需要先锁定另外两个数值，所以对数组先排序。

接下来按步骤走：

1. 从左到右(即从小到大)进行遍历锁定第一个最小数值a，这是第一层循环，a循环时需要去重，避免取到重复的结果
2. 在第一层循环里再嵌套一层循环，从a+1开始遍历数组，锁定第二个数值b，此时 a<b，b循环时需要去重，避免取到重复结果
3. 在第二层循环里设置cd两个指针，c=b+1，d=numslength - 1，类似三数之和，a < b < c < d
4. 对nums的abcd指针值进行相加赋值给sum变量，如果sum>0则d左移，如果sum<0则c右移
5. 如果sum == target，则记录一个结果值，并且需要对cd指针进行移动对c,d指向的值进行去重，避免取到重复结果（注：判断时c<d一定要写在前面） ```go 例如：

必须是这个判断条件 c < d && nums[c+1] == nums[c]

如果是： nums[c+1] == nums[c] && c < d

则会报错，因为c+1可能产生数组越界，会暴毙滴，我试过了

<a name="X9Fpg"></a>
### 解题代码
```go
func fourSum(nums []int, target int) [][]int {
    length := len(nums)
    var result [][]int
    if length < 4 {
        return result
    }
    sort.Ints(nums)
    for a := 0; a < length-3; a++ {
        if a > 0 && nums[a] == nums[a-1] {
            continue
        }
        for b := a + 1; b < length-2; b++ {
            if b > a + 1 && nums[b] == nums[b-1] {
                continue
            }
            c, d := b+1, length-1
            for c < d {
                sum := nums[a] + nums[b] + nums[c] + nums[d]
                if sum > target {
                    d--
                    continue
                } else if sum < target {
                    c++
                    continue
                }
                result = append(result, []int{nums[a], nums[b], nums[c], nums[d]})
                for c < d && nums[c+1] == nums[c] {
                    c++
                }
                for c < d && nums[d-1] == nums[d] {
                    d--
                }
                c++
                d--
            }
        }
    }
    return result
}