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



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

3f44fd2740fcd2ff5c9a22b09e88b03c.png


给定一个整数数组,让我们求数组元素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


Vote Vote Cancel Collect Collect Cancel

<< 上一篇: Leetcode基础刷题之PHP解析(14. Longest Common Prefix)

>> 下一篇: Leetcode基础刷题之PHP解析(16. 3Sum Closest)