2019-06-26 吴亲库里 库里的深夜食堂
给定一个数组，求出四个数加起来等于给定目标值值的全部组合，当然还是不能有重复的组合。
****
不得不佩服这些出题的人，leetcode每一个题目都会有千变万化的题型。这道题我们需要先化简，把四个数相加等于目标值换成两个数相加等于目标值，这则么化？其实道理小学的时候就学过。比如说我要算10+20+30+40==100？(不好意思我口算不出来)，100就是我们的目标数。可以先转换成100-10-20产生一个新的目标数，剩下的工作就是30+40 ？=70？整体的思路就是这样。
但是这个过程我们处理很多信息，第一给定的数组是无序的，我们先转为有序，相加的过程中一个向左边移动一个向右边移动(左小右大)，直到左右相遇，一但发现sum值加起来大于目标数，那么说明右边给的值太大了，往左边移动。反之左边的往右边移动。如果相等说明这是其中的一组解，把这组解push到最终返回的数组里面。另外一点就是要求不能重复，如果下一个位置的值和上一位置的值是相等的，那么直接跳过去。
/**
* @param Integer[] $nums
* @param Integer $target
* @return Integer[][]
*/
function fourSum($nums, $target) {
$result=[];
if(count($nums)<4) return $result;
sort($nums);
$count=count($nums);
for($i=0;$i<$count-3;$i++){
if($i==0 || $nums[$i] !== $nums[$i-1]){
for($j=$i+1;$j<$count-2;$j++){
if($j==$i+1 || $nums[$j] !== $nums[$j-1]){
$newTarget=$target-$nums[$i]-$nums[$j];
$start=$j+1;
$end=$count-1;
while($start<$end){
if($nums[$start]+$nums[$end]==$newTarget){
$result[]=[$nums[$i],$nums[$j],$nums[$start],$nums[$end]];
while($start<$end && $nums[$start]==$nums[$start+1]) $start++;
$start++;
while($start<$end && $nums[$end]==$nums[$end-1]) $end--;
$end--;
}else if($nums[$start]+$nums[$end]>$newTarget){
$end--;
} else $start++;
}
}
}
}
}
return $result;
}
