Leetcode力扣算法题目——四数之和

给定一个包含 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);
    }

}

代码执行结果

image.png

小小总结

菜鸟的我一看到这道题一下子想到了用排列组合的方法，但缺乏考虑的是内存的限制

image.png

根据组合的公式，假设数组有一百个数，求四数之和，那就是要计算100 * 99 * 98 * 97 / 12 = 7842450次得到满足条件的所有数组，后续还有操作未执行....细思极恐啊。难怪内存超出限制执行异常。

优化后的方法看起来简单又高效，最后占用内存15M不到，简直是大大提升。