上 一 题 链 接 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基础入门之模块解析(二)
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。