18. 四数之和

题意：

解题思路：

思路：
    1. (三重枚举，无重复构造) O(n3)
    2. 在 3Sum 算法的思路，排序后再增加一重循环即可。

PHP代码实现：

class Solution {
    function fourSum($nums, $target) {
        if (!$nums) return [];
        sort($nums);
        $ret = [];
        for ($i = 0; $i < count($nums) - 3; $i++) {
            if ($i > 0 && $nums[$i] == $nums[$i - 1]) continue;
            for ($j = $i + 1; $j < count($nums) - 2; $j++) {
                if ($j > $i + 1 && $nums[$j] == $nums[$j - 1]) continue;
                $left = $j + 1;
                $right = count($nums) - 1;
                while ($left < $right) {
                    $sum = $nums[$i] + $nums[$j] + $nums[$left] + $nums[$right];
                    if ($sum == $target) {
                        array_push($ret, [$nums[$i], $nums[$j], $nums[$left], $nums[$right]]);
                        while ($left < $right && $nums[$left] == $nums[$left + 1]) $left++;
                        while ($left < $right && $nums[$right] == $nums[$right - 1]) $right--;
                        $left++; $right--;
                    } else if ($sum > $target) {
                        $right--;
                    } else $left++;
                }
            }
        }
        return $ret;
    }
}

GO代码实现：

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