上 一 题 链 接 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
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- Apache Flink 零基础入门(一):基础概念解析
- Apache Flink 零基础入门(一):基础概念解析
- JStorm 源码解析:基础线程模型
- React Hooks 解析(上):基础
- TypeScript基础入门之模块解析(一)
- TypeScript基础入门之模块解析(二)
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
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》 这本书的介绍吧!