专栏首页小浩算法漫画:经典鹅厂面试题(4sum - nSum)

漫画:经典鹅厂面试题(4sum - nSum)

今天是小浩算法“365刷题计划”第79天。为大家讲解三数之和的进阶版本 - 四数之和。

建议先回顾一下该题前两个版本:

漫画:两数之和

漫画:经典鹅厂面试题(2Sum,3Sum,4Sum)

01

PART

四数之和

本题是 三数之和 的进阶版本。

第18题:给定一个包含 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]

]

02

PART

题目分析

对于四数之和,其实和三数之和差别不大,仍然采用双指针来求解即可。

之前有人问我“三数之和我知道通过固定一个元素,使用双指针遍历进行求解,但是四数之和我就搞不清楚如何固定元素了怎么办”其实这个本质上还是一样的,一起来看下:

假若数组为 [1, 0, -1, 0, -2, 2],这样:

我们第一步肯定还是先排序(这个在三数之和里也讲了,排序的目的有两个:1、方便跳过重复元素 2、可以利用排序的特性,直接过滤掉重复计算

排完序的数组长这样:

然后下来就是设置我们需要的四个值了:(待固定的两个值,以及双指针)

其实固定的方法还是一样,因为我们已经固定了 i,只需要对 i+1 就可以得到我们待固定的 j。放在代码里,其实就是多了一个嵌套循环。然后差不多可以给出下面的代码代码结构:

for (int i = 0; i < n - 3; i++) {
    //特殊处理-1
    if (i > 0 && nums[i] == nums[i - 1]) continue;
    if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
    if (nums[i] + nums[n - 1] + nums[n - 2] + nums[n - 3] < target) continue;
    for (int j = i + 1; j < n - 2; j++) {
        //特殊处理-2
        if (j - i > 1 && nums[j] == nums[j - 1]) continue;
        if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break;
        if (nums[i] + nums[j] + nums[n - 1] + nums[n - 2] < target) continue;
        int left = j + 1;
        int right = n - 1;
        while (left < right) {
            //双指针循环查找
        }
    }

当然,这个结构里,除了对四个值的定义,我们还加了两段特殊处理的逻辑。分别是 3-5 行 和 8-10 行。这是什么意思呢:

  • 第 3 行和第 8 行分别处理了 i 和 j 重复值的情况。
  • 第 4-5 和 9-10 就是我们上面说的,利用排序的特性,直接过滤掉重复计算了。

因为题目中已经要求了,不允许出现重复值,所以第3行和第8行肯定是不可以去掉的,但是题目中没说非得利用排序的特性对不?那一会儿我们就可以尝试把 4-5 和 9-10 去掉,看看会不会报错,这个一会儿再说。

剩下的逻辑就是在双指针循环体内查找另外两个元素了。自然这里我们也得处理重复值(第7行和第8行),到这里细心的读者会发现,其实和三数之和已经差不多了!

//JAVA
while (left < right) {
    int tmp = nums[i] + nums[j] + nums[left] + nums[right];
    if (tmp == target) {
        List<Integer> tmpList = new LinkedList<>(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
        res.add(tmpList);
        while (left < right && nums[left] == nums[left + 1]) left += 1;
        while (left < right && nums[right] == nums[right - 1]) right -= 1;
        left += 1;
        right -= 1;
    } else if (tmp > target) right -= 1;
    else left += 1;
}

剩下的自然就是拼装代码了:

//JAVA
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new LinkedList<>();
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
            if (nums[i] + nums[n - 1] + nums[n - 2] + nums[n - 3] < target) continue;
            for (int j = i + 1; j < n - 2; j++) {
                if (j - i > 1 && nums[j] == nums[j - 1]) continue;
                if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break;
                if (nums[i] + nums[j] + nums[n - 1] + nums[n - 2] < target) continue;
                int left = j + 1;
                int right = n - 1;
                while (left < right) {
                    int tmp = nums[i] + nums[j] + nums[left] + nums[right];
                    if (tmp == target) {
                        List<Integer> tmpList = new LinkedList<>(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        res.add(tmpList);
                        while (left < right && nums[left] == nums[left + 1]) left += 1;
                        while (left < right && nums[right] == nums[right - 1]) right -= 1;
                        left += 1;
                        right -= 1;
                    } else if (tmp > target) right -= 1;
                    else left += 1;
                }
            }

        }
        return res; 
    }
}

然后跑一跑,发现还不错:

然后我们再尝试把刚才说的“避免重复计算”的代码去掉:

//JAVA
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new LinkedList<>();
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < n - 2; j++) {
                if (j - i > 1 && nums[j] == nums[j - 1]) continue;
                int left = j + 1;
                int right = n - 1;
                while (left < right) {
                    int tmp = nums[i] + nums[j] + nums[left] + nums[right];
                    if (tmp == target) {
                        List<Integer> tmpList = new LinkedList<>(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        res.add(tmpList);
                        while (left < right && nums[left] == nums[left + 1]) left += 1;
                        while (left < right && nums[right] == nums[right - 1]) right -= 1;
                        left += 1;
                        right -= 1;
                    } else if (tmp > target) right -= 1;
                    else left += 1;
                }
            }
        }
        return res; 
    }
}

发现也是不会报错的,但是性能就大打折扣了:

郑重申明(读我的文章必看):

  • 本系列所有教程都不会用到复杂的语言特性,大家无须担心没有学过相关语法,算法思想才是最重要的!
  • 作为学术文章,虽然风格可以风趣,但严谨,我是认真的。本文所有代码均在leetcode进行过测试运行。

03

PART

结尾

其实四数之和已经比较麻烦了,但是如果面试的时候对方问到N数之和,这个时候其实也不用着急。一般来讲,N数之和 是不会让你写的。只需要把上面的代码转化成递归的形式,答出来通过递归每次固定N-2个数就可以了。

2sum,3sum,4sum 系列篇 到这里就结束了。这里边 2sum 和 3sum 还是非常建议大家去练习一下的。算法这个东西,思想是一回事,动手是另一回事。长路漫漫磕磕绊绊,难受就是提高。

本文分享自微信公众号 - 小浩算法(xuesuanfa),作者:程序员浩哥

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

原始发表时间:2020-04-07

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 漫画:常考的荷兰国旗问题你还不会吗?(初级)

    "荷兰国旗问题" 是计算机科学中的一个经典题目,它是由Edsger Dijkstra提出的。荷兰国旗由红、白、蓝三色组成。

    程序员小浩
  • 漫画:经典鹅厂面试题(2Sum,3Sum,4Sum)

    该题为 二数之和 的进阶版本,当然还有一个进阶版本为 四数之和。我们将会一一进行分析!

    程序员小浩
  • 漫画:美团面试题(TOPK:求第K个最大的元素)

    这个题目的变形很多,比如找 "前 K 个高频元素"、 "数据流中的第K大元素" 、"最接近原点的 K 个值" 等等等等。

    程序员小浩
  • 双指针法:一样的道理,能解决四数之和

    题意:给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c ...

    代码随想录
  • LeetCode-15 三数之和

    今天我们学习第15题三数之和,这是一道中等题。像这样字符串的题目经常作为面试题来考察面试者算法能力和写代码能力,因此最好能手写出该题。下面我们看看这道题...

    用户3470542
  • LeetCode-18 四数之和

    今天我们学习第18题四数之和,这是一道中等题。像这样数组的题目经常作为面试题来考察面试者算法能力和写代码能力,因此最好能手写出该题。下面我们看看这道题的...

    用户3470542
  • Python3刷题系列(三)

    中文版:https://leetcode-cn.com/problems/sqrtx/

    用户5473628
  • 【python-leetcode15-双指针】三个数之和为零

    给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组...

    绝命生
  • 漫画:经典鹅厂面试题(2Sum,3Sum,4Sum)

    该题为 二数之和 的进阶版本,当然还有一个进阶版本为 四数之和。我们将会一一进行分析!

    程序员小浩
  • LeetCode-31-Next-Permutation

    这个排序主要是有两种情况,一个是类似于3 1 2这样的情况,直接从后往前找到第一个nums[i]<nums[i-1]的,然后把i记下来,再与后面第一个小于i的k...

    小二三不乌

扫码关注云+社区

领取腾讯云代金券