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


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

查看所有标签

猜你喜欢:

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

An Introduction to Genetic Algorithms

An Introduction to Genetic Algorithms

Melanie Mitchell / MIT Press / 1998-2-6 / USD 45.00

Genetic algorithms have been used in science and engineering as adaptive algorithms for solving practical problems and as computational models of natural evolutionary systems. This brief, accessible i......一起来看看 《An Introduction to Genetic Algorithms》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具