在看计算四数之和的时候看先看看两个数、三个数求和是怎样的。
两数之和
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
class Solution {
/**
* @param Integer[] $nums
* @param Integer $target
* @return Integer[]
*/
function twoSum($nums, $target) {
$len = count($nums);
$res = [];
for($i = 0; $i < $len -1 ; $i++) {
for($j = $i + 1; $j < $len ; $j ++) {
if($nums[$i] + $nums[$j] == $target) {
$res = [$i, $j];
}
}
}
return array_unique($res, SORT_REGULAR);
}
}
给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]
class Solution {
/**
* @param Integer[] $nums
* @return Integer[][]
*/
function threeSum($nums) {
sort($nums);
$len = count($nums);
$res = [];
for($i = 0; $i < $len -2; $i ++) {
$l = $i + 1;
$r = $len - 1;
while ($l < $r) {
$sum = $nums[$i] + $nums[$l] + $nums[$r];
if ($sum === 0 && $r > $l) {
$tmp = [$nums[$i], $nums[$l], $nums[$r]];
$res[] = $tmp;
while ($l < $r && $nums[$r] === $nums[$r - 1]) {
$r--;
}
while ($l < $r && $nums[$l] === $nums[$l + 1]) {
$l++;
}
$r--;
$l++;
} else {
if ($sum > 0) {
$r--;
} else {
$l++;
}
}
}
}
return array_unique($res, SORT_REGULAR);
}
}
给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组。
注意:答案中不可以包含重复的四元组。
示例:
给定数组 nums = [1, 0, -1, 0, -2, 2],和 target = 0。
满足要求的四元组集合为:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
我这边使用的是php语言排列组合的递归方法,得出所有四个数的集合,在对每一个数组进行求和与目标数相比。
class Solution {
/**
* @param Integer[] $nums
* @param Integer $target
* @return Integer[][]
*/
function fourSum($nums, $target) {
$result = [];
$com_array = self::combination($nums, 4);
foreach($com_array as $arr) {
if (array_sum($arr) === $target && is_array($arr)) {
sort($arr);
$result[] = $arr;
}
}
return array_unique($result, SORT_REGULAR);
}
function combination($st_array, $m) {
$re_array = array();
$n = count($st_array);
if ($m <= 0 || $m > $n) {
return $re_array;
}
for ($i=0; $i<$n; $i++) {
$t = array($st_array[$i]);
if ($m == 1) {
$re_array[] = $t;
} else {
$item_array = array_slice($st_array, $i+1);
$c = self::combination($item_array, $m-1);
foreach ($c as $v) {
$re_array[] = array_merge($t, $v);
}
}
}
return $re_array;
}
}
image.png
设置了 ini_set('memory_limit','256M'); 512M,1024M均不行,力扣官网测试用例在不断的增加数组的长度,导致内存原因执行失败。
Line 36: PHP Fatal error: Allowed memory size of 536870912 bytes exhausted (tried to allocate 67108872 bytes) in solution.php
优化后:
class Solution {
/**
* @param Integer[] $nums
* @param Integer $target
* @return Integer[][]
*/
function fourSum($nums, $target)
{
sort($nums);
$len = count($nums);
$res = [];
for ($i = 0; $i < $len - 3; $i++) {
for ($j = $i + 1; $j < $len - 2; $j++) {
$l = $j + 1;
$r = $len - 1;
while ($l < $r) {
$sum = $nums[$i] + $nums[$j] + $nums[$l] + $nums[$r];
if ($sum === $target && $r > $l) {
$tmp = [$nums[$i], $nums[$j], $nums[$l], $nums[$r]];
$res[] = $tmp;
while ($l < $r && $nums[$r] === $nums[$r - 1]) {
$r--;
}
while ($l < $r && $nums[$l] === $nums[$l + 1]) {
$l++;
}
$r--;
$l++;
} else {
if ($sum > $target) {
$r--;
} else {
$l++;
}
}
}
}
}
return array_unique($res, SORT_REGULAR);
}
}