专栏首页程序员的碎碎念Leetcode力扣算法题目——四数的和

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);
    }

}

本文分享自微信公众号 - 程序员的碎碎念(gh_53e607dd4782),作者:沙蒿

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-08-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 每日一题169: 求众数

    给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

    benny
  • LeetCode每日一题53: 最大子序和

    给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

    benny
  • ThinkPHP+PHPExcel实现excel导入导出数据(一)

    没错,今天又将是一篇技术帖,一篇关于tp进阶学习的教程,看标题你就知道我要做的是什么啦? 首先我带大家科普一下什么是phpexcel? ? ...

    benny
  • LeetCode 图解 | 18.四数之和

    今天分享的题目来源于 LeetCode 第 18 号题:四数之和,题目标签是:散列表、双指针和数组。

    五分钟学算法
  • LeetCode动画 | 18.通过散列表解四数之和

    今天分享一个LeetCode题,题号是18,标题是:四数之和,题目标签是:散列表、双指针和数组。此文通过散列表和双指针两种方式解决此题,分别画了动画视频,注意收...

    我脱下短袖
  • Python3刷题系列(七)

    https://leetcode.com/problems/different-ways-to-add-parentheses/

    用户5473628
  • Leetcode 162 Find Peak Element

    A peak element is an element that is greater than its neighbors. Given an inpu...

    triplebee
  • LeetCode - 搜索插入位置

    LeetCode第35题,难度简单。接下去的题目可能会慢慢变成两三年之前做的题目了....清完库存我再接着解题,写题解...

    晓痴
  • 寻找旋转排序数组中的最小值

    一份执着✘
  • LeetCode 1. Two Sum分析代码

    利用hashmap存储每个元素的值和所在的下标,遍历一遍,如果target-nums[i]在map里直接取出index值返回就可以了。leetcode 的第一道...

    desperate633

扫码关注云+社区

领取腾讯云代金券