把稳:答案中不可以包含重复的四元组。
示例:给天命组 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; }}
涌现问题-超出内存限定
设置了 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); }}
代码实行结果
菜鸟的我一看到这道题一下子想到了用排列组合的方法,但缺少考虑的是内存的限定
根据组合的公式,假设数组有一百个数,求四数之和,那便是要打算100 99 98 97 / 12 = 7842450次得到知足条件的所有数组,后续还有操作未实行....细思极恐啊。难怪内存超出限定实行非常。
优化后的方法看起来大略又高效,末了占用内存15M不到,切实其实是大大提升。