Leetcode基础刷题之PHP解析(15. 3Sum)

上一题链接Leetcode基础刷题之PHP解析(14. Longest Common Prefix)

题目描述

给定一个整数数组，让我们求数组元素a,b,c加起来等于0的所有组合，当然不能重复。

题目分析

这道题真的麻烦的要死,由于给定的数组不是有序的，如果是这样的话，那么我们就要很死板的把所有的组合全走一遍，这样当然不行，我们先将数组排序。这样有多少好处?比如如果是有序的话，当遍历到某个点上，三个值加起来大于0，那么可以直接break了，因为之后的数加起来肯定都大于0了，如果加起来小于0的话，那么直接进入下一层循环，如果当前的数和下一个数是一样的话，不用想了跳过吧。这是可以优化的一个点。

第二个可以优化的点，我们不一定要很死板的在i,i+1,i+2的位置上进行运算，我们可以一个点在i+1,一个点在cout($nums)-1上，也就是一个往右一个向左，直到相遇，结束。还有一点就是循环的时候到count($nums)-2这个位置就行了，因为每次要拿三个数进行计算，后面两层循环是没有意义的。

/**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function threeSum($nums) {
       
        $count=count($nums);
        $result=[];
        sort($nums);
        for($i=0;$i<$count-2;$i++){
            if($nums[$i]+$nums[$i+1]+$nums[$i+2]>0) break;
            if($nums[$i]+$nums[$count-2]+$nums[$count-1]<0) continue;
            if($i>0 && $nums[$i]==$nums[$i-1]) continue;
            $l=$i+1;
            $r=$count-1;
           
            while($l<$r){
                $temp=$nums[$i]+$nums[$l]+$nums[$r];
                
                if($temp==0){
                    $result[]=[$nums[$i],$nums[$l],$nums[$r]];
                   
                    while($l+1<$r && $nums[$l]==$nums[$l+1]){
                        $l +=1;
                    }
                    $l +=1;
                    while($r-1>$l && $nums[$r]==$nums[$r-1]){
                        $r -=1;
                    }
                    $r -=1;
                }elseif($temp>0){
                    $r -=1;
                }else $l +=1;
            }
            
        }
        return $result;
    }

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