源题目

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

18. 四数之和

难度中等919
给你一个由 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

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

示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
输入：nums = [2,2,2,2,2], target = 8 输出：[[2,2,2,2]]

提示：

• 1 <= nums.length <= 200
• -109 <= nums[i] <= 109
• -109 <= target <= 109

class Solution {
    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[][]
     */
    function fourSum($nums, $target) {
        //先排序，再双指针
        sort($nums);
        $len = count($nums);
        $ret = [];
        //小于3根本构不成三元组，直接返回错误
        if($len < 4) return $ret;
        //在三数之和的基础上多套一层循环
        for($i = 0; $i < $len -3; ++$i){
            //去重操作
            if($i>0 && $nums[$i] == $nums[$i - 1]) continue;
            for($j = $i+1; $j<$len -2;++$j){
                //去重操作
                if($j>$i+1 && $nums[$j] == $nums[$j - 1]) continue;
                $left = $j +1;//左指针
                $right = $len -1;//右指针
                while($left < $right){
                    //四数相加
                    $sum = $nums[$i] + $nums[$j] + $nums[$left] + $nums[$right];
                    if($sum == $target){
                        //满足条件时，将四元组压入结果数组
                        $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){
                        //a+b+c=0====>a+b=-c
                        $left ++;
                    }else{
                        $right --;
                    }
                }
            }
        }
        return $ret;
    }
}