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

栏目: 编程工具 · 发布时间: 5年前

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

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

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


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

组合数学

组合数学

Richard A.Brualdi / 机械工业出版社 / 2009-3 / 49.00元

《组合数学(英文版)(第5版)》英文影印版由Pearson Education Asia Ltd.授权机械工业出版社独家出版。未经出版者书面许可,不得以任何方式复制或抄袭奉巾内容。仅限于中华人民共和国境内(不包括中国香港、澳门特别行政区和中同台湾地区)销售发行。《组合数学(英文版)(第5版)》封面贴有Pearson Education(培生教育出版集团)激光防伪标签,无标签者不得销售。Englis......一起来看看 《组合数学》 这本书的介绍吧!

URL 编码/解码
URL 编码/解码

URL 编码/解码

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具