关于PHP求解三数之和问题详析
三数之和
给你一个包含n个整数的数组nums，判断nums中是否存在三个元素a，b，c，使得a+b+c=0？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组nums=[-1,0,1,2,-1,-4]， 满足要求的三元组集合为： [ [-1,0,1], [-1,-1,2] ]
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/3sum
解题思路1
暴力枚举法，三层for+if判断就可以了，这样作面试中offer会成为别人的。不写代码了，数据量大了也容易超时。
解题思路2
可以先固定一个值，然后寻找后两个值时可采取双指针的方法，将总的时间复杂度优化到O(n^2)。
实现的过程中，要注意优化以及去重。
首先我们先对原数组进行排序，这样可以把重复的值集中到一起，便于去重。
确定第一个元素时，如果它已经比0大了，那么可以直接跳出循环，因为后面的数字都比它大。如[1,2,3,4],i=0,nums[i]>0,这样是不可能产生合法的情况的，直接break。
确定第一个元素时，如果发现它与它前面的值一样，那么跳过本轮。如[-1,-1,0,1],在第一轮后，已经选出了{-1,0,1},现在i=1，nums[i]==nums[i-1],为了避免重复，直接continue。
接下来利用双指针，left指向i+1,right指向count($nums)-1。逐个进行判断，并注意去重。有点类似于固定在一个值，然后剩下的用双指针求两数之和。
classSolution{
/***@paramInteger[]$nums*@returnInteger[][]*/
functionthreeSum($nums){
$result=[];
$count=count($nums);
if($nums===null||count($nums)<=2)return$result;
sort($nums);//O(nlogn)
for($i=0;$i<$count-2;$i++){//O(n^2)
if($nums[$i]>0)break;//第一个数大于0，后面的数都比它大，肯定不成立了
if($i>0&&$nums[$i]===$nums[$i-1])continue;//去掉重复情况
$target=-$nums[$i];
$left=$i+1;
$right=$count-1;
while($left<$right){
if($nums[$left]+$nums[$right]===$target){
$result[]=[$nums[$i],$nums[$left],$nums[$right]];
//现在要增加left，减小right，但是不能重复，比如:[-2,-1,-1,-1,3,3,3],i=0,left=1,right=6,[-2,-1,3]的答案加入后，需要排除重复的-1和3
$left++;
$right--;//首先无论如何先要进行加减操作
while($left<$right&&$nums[$left]===$nums[$left-1])$left++;
while($left<$right&&$nums[$right]===$nums[$right+1])$right--;
}elseif($nums[$left]+$nums[$right]<$target){
$left++;
}else{//$nums[$left]+$nums[$right]>$target
$right--;
}
}
}
return$result;
}
}
参考链接：
- 三数之和的官方题解和高赞答案
- 极客时间算法面试通关40讲
到此这篇关于PHP求解三数之和问题的文章就介绍到这了,更多相关PHP求解三数之和内容请搜索毛票票以前的文章或继续浏览下面的相关文章希望大家以后多多支持毛票票！