Leetcode力扣算法题目——四数的和
在看计算四数之和的时候看先看看两个数、三个数求和是怎样的。
两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]PHP代码实现
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]
]PHP代码实现
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);
}
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-08-11，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录