Leetcode基础刷题之PHP解析(18. 4Sum)

 2019-6-26 星期三 开始吧

上一题链接Leetcode基础刷题之PHP解析(16. 3Sum Closest)

题目描述

给定一个数组，求出四个数加起来等于给定目标值值的全部组合，当然还是不能有重复的组合。

题目分析

不得不佩服这些出题的人，leetcode每一个题目都会有千变万化的题型。这道题我们需要先化简，把四个数相加等于目标值换成两个数相加等于目标值，这则么化？其实道理小学的时候就学过。比如说我要算10+20+30+40==100？(不好意思我口算不出来)，100就是我们的目标数。可以先转换成100-10-20产生一个新的目标数，剩下的工作就是30+40 ？=70？整体的思路就是这样。

但是这个过程我们处理很多信息，第一给定的数组是无序的，我们先转为有序，相加的过程中一个向左边移动一个向右边移动(左小右大)，直到左右相遇，一但发现sum值加起来大于目标数，那么说明右边给的值太大了，往左边移动。反之左边的往右边移动。如果相等说明这是其中的一组解，把这组解push到最终返回的数组里面。另外一点就是要求不能重复，如果下一个位置的值和上一位置的值是相等的，那么直接跳过去。

  /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[][]
     */
    function fourSum($nums, $target) {
        $result=[];
        if(count($nums)<4) return $result;
        sort($nums);
        $count=count($nums);
        for($i=0;$i<$count-3;$i++){
            if($i==0 || $nums[$i] !== $nums[$i-1]){
                for($j=$i+1;$j<$count-2;$j++){
                    if($j==$i+1 || $nums[$j] !== $nums[$j-1]){
                        $newTarget=$target-$nums[$i]-$nums[$j];
                        $start=$j+1;
                        $end=$count-1;
                        while($start<$end){
                         if($nums[$start]+$nums[$end]==$newTarget){
                            $result[]=[$nums[$i],$nums[$j],$nums[$start],$nums[$end]];
                            while($start<$end && $nums[$start]==$nums[$start+1]) $start++;
                            $start++;
                            while($start<$end && $nums[$end]==$nums[$end-1]) $end--;
                            $end--;
                        }else if($nums[$start]+$nums[$end]>$newTarget){
                            $end--;
                        } else $start++;
                             
                    }
                       
                 }
              }
            }
        }
        return $result;
    }

Github整理地址:https://github.com/wuqinqiang/leetcode-php