专栏首页小浩算法漫画:经典鹅厂面试题(2Sum,3Sum,4Sum)

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

今天是小浩算法“365刷题计划”第77天。讲解一道经典鹅厂面试题,有一定难度。

建议先回顾一下该题简化版,二数之和:

01

PART

三数之和

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

第15题:给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。注意:答案中不可以包含重复的三元组。

示例:

给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为:

[

[-1, 0, 1],

[-1, -1, 2]

]

02

PART

题目分析

本题的暴力题解可以仿照二数之和,直接三层遍历,取和为0的三元组,并记录下来,最后再去重。但是作为一个有智慧的人,我们不能这么去做。

因为我们的目标是找数,当然使用指针的方式最简单。假若我们的数组为:

[-1, 0, 1, 2, -1, -4]

求解过程如下:首先我们先把数组排个序(原因一会儿说),排完序长这样:

因为我们要同时找三个数,所以采取固定一个数,同时用双指针来查找另外两个数的方式。所以初始化时,我们选择固定第一个元素(当然,这一轮走完了,这个蓝框框我们就要也往前移动),同时将下一个元素和末尾元素分别设上 left 和 right 指针。画出图来就是下面这个样子:

现在已经找到了三个数,当然是计算其三值是否满足三元组。但是这里因为我们已经排好了序,如果固定下来的数(上面蓝色框框)本身就大于 0,那三数之和必然无法等于 0。比如下面这种:

然后自然用脚指头也能想到,我们需要移动指针。现在我们的排序就发挥出用处了,如果和大于0,那就说明 right 的值太大,需要左移。如果和小于0,那就说明 left 的值太小,需要右移。(上面这个思考过程是本题的核心) 整个过程如下图所示:

其中:在第6行时,因为三数之和大于0,所以right进行了左移。最后一行,跳过了重复的-1。

然后啰嗦一句,因为我们需要处理重复值的情况。除了固定下来的i值(蓝框框),left 和 right 当然也是需要处理重复的情况,所以对于 left 和 left+1,以及 right 和 right-1,我们都单独做一下重复值的处理。(其实没啥处理,就是简单的跳过)

03

PART

代码展示

四数之和其实与本题解法差不太多,把固定一个数变成两个,同样还是使用双指针进行求解就可以了。

根据上面的分析,顺利得出代码(给一个Java版本的):

//JAVA
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList();
        for (int i = 0; i < nums.length; i++) {
            int target = 0 - nums[i];
            int l = i + 1;
            int r = nums.length - 1;
            if (nums[i] > 0)
                break;
            if (i == 0 || nums[i] != nums[i - 1]) {
                while (l < r) {
                    if (nums[l] + nums[r] == target) {
                        res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                        while (l < r && nums[l] == nums[l + 1]) l++;
                        while (l < r && nums[r] == nums[r - 1]) r--;
                        l++;
                        r--;
                    } else if (nums[l] + nums[r] < target)
                        l++;
                    else
                        r--;
                }
            }
        }
        return res;
    }
}

给一个python版本的(这个我就直接拿别人的代码了,思想都一样)

//python
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n=len(nums)
        res=[]
        if(not nums or n<3):
            return []
        nums.sort()
        res=[]
        for i in range(n):
            if(nums[i]>0):
                return res
            if(i>0 and nums[i]==nums[i-1]):
                continue
            L=i+1
            R=n-1
            while(L<R):
                if(nums[i]+nums[L]+nums[R]==0):
                    res.append([nums[i],nums[L],nums[R]])
                    while(L<R and nums[L]==nums[L+1]):
                        L=L+1
                    while(L<R and nums[R]==nums[R-1]):
                        R=R-1
                    L=L+1
                    R=R-1
                elif(nums[i]+nums[L]+nums[R]>0):
                    R=R-1
                else:
                    L=L+1
        return res

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

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

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

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

    程序员小浩
  • 漫画:经典鹅厂面试题(4sum - nSum)

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

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

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

    程序员小浩
  • 【python-leetcode15-双指针】三个数之和为零

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

    绝命生
  • 【每日算法Day 75】字节跳动面试题:手撕困难题,看过我Day 71的人都会做了!

    韦阳的博客:【每日算法Day 71】面试官想考我这道位运算题,结果我给出了三种解法[2]

    godweiyang
  • 【leetcode】15:三数之和

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

    帅地
  • LeetCode-下一个排列

    感觉从之前的题目开始写起来的话,会需要一定的时间去思考当时为什么这么写,那么每次写都是重新思考,除非进度能够赶上最新的刷题进度,所以决定从最新的开始往前写......

    晓痴
  • LeetCode - 4数之和

    今天才发现,上周在钉钉上面加我的阿里同学,就是给我发offer的HR,而我当时并不知道,只知道去骚扰其他的HR问结果。

    晓痴
  • Leetcde Golang 26. Remove Duplicates from Sorted Array.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/88902453

    anakinsun
  • Leetcode Golang 75. Sort Colors.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/arti...

    anakinsun

扫码关注云+社区

领取腾讯云代金券