当前播放: 16 | 面试题:三数之和
00:00 / 00:00
高清
  • 高清
1.0x
  • 2.0x
  • 1.5x
  • 1.25x
  • 1.0x
  • 0.5x
网页全屏
全屏
00:00
付费课程,可试看
课程目录
第一章:课程综述 (4讲)
01 | 合格程序员的第一步:算法与数据结构
免费
02 | 如何事半功倍地学习算法与数据结构
免费
03 | 如何计算算法的复杂度
免费
04 | 如何通过LeetCode来进行算法题目练习
免费
第二章:理论讲解+面试题实战 (53讲)
05 | 理论讲解:数组&链表
免费
06 | 面试题:反转一个单链表&判断链表是否有环
07 | 理论讲解:堆栈&队列
08 | 面试题:判断括号字符串是否有效
09 | 面试题:用队列实现栈&用栈实现队列
10 | 理论讲解:优先队列
11 | 面试题:返回数据流中的第K大元素
12 | 面试题:返回滑动窗口中的最大值
13 | 理论讲解:哈希表
14 | 面试题:有效的字母异位词
15 | 面试题:两数之和
16 | 面试题:三数之和
17 | 理论讲解:树&二叉树&二叉搜索树
18 | 面试题:验证二叉搜索树
19 | 面试题:二叉树&二叉搜索树的最近公共祖先
20 | 理论讲解:二叉树遍历
21 | 理论讲解:递归&分治
22 | 面试题:Pow(x,n)
23 | 面试题:求众数
24 | 理论讲解:贪心算法
25 | 面试题:买卖股票的最佳时机
26 | 理论讲解:广度优先搜索
27 | 理论讲解:深度优先搜索
28 | 面试题:二叉树层次遍历
29 | 面试题:二叉树的最大和最小深度
30 | 面试题:生成有效括号组合
31 | 理论讲解:剪枝
32 | 面试题:N皇后问题
33 | 面试题:数独问题
34 | 理论讲解:二分查找
35 | 面试题:实现一个求解平方根的函数
36 | 理论讲解:字典树
37 | 面试题:实现一个字典树
38 | 面试题:二维网格中的单词搜索问题
39 | 理论讲解:位运算
40 | 面试题:统计位1的个数
41 | 面试题:2的幂次方问题&比特位计数问题
42 | 面试题:N皇后问题的另一种解法
43 | 理论理解:动态规划(上)
44 | 理论理解:动态规划(下)
45 | 面试题:爬楼梯
46 | 面试题:三角形的最小路径和
47 | 面试题:乘积最大子序列
48 | 面试题:股票买卖系列
49 | 面试题:最长上升子序列
50 | 面试题:零钱兑换
51 | 面试题:编辑距离
52 | 理论讲解:并查集
53 | 面试题:岛屿的个数&朋友圈(上)
54 | 面试题:岛屿的个数&朋友圈(下)
55 | 理论讲解: LRU Cache
56 | 面试题:设计和实现一个LRU Cache缓存机制
57 | 理论讲解:布隆过滤器
第三章:课程总结 (5讲)
58 | 课程重点回顾
59 | FAQ答疑&面试中切题四件套
60 | 回到起点:斐波拉契数列
61 | 白板实战番外篇:斐波拉契数列
62 | 最后的一些经验分享
16 | 面试题:三数之和

16 | 面试题:三数之和

覃超
Sophon Tech创始人,前Facebook工程师,卡内基梅隆大学计算机硕士
62讲 62课时·约600分钟18974
单独订阅¥129
2人成团¥99
23
登录 后留言

精选留言(38)

  • XUN
    这个是不是没有考虑“不重复的”三元组这个条件?
    2018-10-28
    1
    16
  • 柠檬C
    老师,可以提供一下java语言的第一种解法吗…😂一直没法去重
    2018-10-28
    2
    13
  • 💤 ZZzz💤
    第二种解法用set无法解决,这里用map来替代,不过性能真的很一般
    public List<List<Integer>> threeSum(int[] nums) {
            if(nums ==null || nums.length == 0){
                return new ArrayList();
            }
            List<List<Integer>> resultList = new ArrayList();
            //要先对数组进行排序
            Arrays.sort(nums);
            for(int i=0;i<nums.length-1;i++){
                //重复的过滤掉
                if(i>0 && nums[i] == nums[i-1])
                    continue;
                Map<Integer,Integer> targetMap = new HashMap<>();
                for(int j=i+1;j<nums.length;j++){
                    if(targetMap.containsKey(nums[j])){
                        if(targetMap.get(nums[j]) == 0){
                            resultList.add(Arrays.asList(nums[i],nums[j],-nums[i] - nums[j]));
                            targetMap.put(nums[j],1);
                        }
                    }else{
                        targetMap.put(-nums[i] - nums[j],0);
                    }
                }
            }
            return resultList;
        }
    2019-01-12
    4
  • tinys
    关于第二种解法...
    由于给出的数组不排除重复数,比如-1,-1,2这种..
    按照你前面小白板的说法是直接将数组扔到set去判断...
    但这种情况在假设我们只有-1,2而木有第三个-1这个数时也是可以得出{-1,-1,2}这个解的..

    ps你后面py代码我没太看懂,,,

    作者回复: 这是代码实现的一个细节问题:在遍历的时候,需要把当前遍历元素从set里去掉;每次遍历完一个元素再将其加回到set中。

    2018-10-27
    4
  • farFlight
    第一种解法没看明白。。自己拓展2sum的写了3sum和4sum,感觉hashset/map解法很麻烦,而且用python写很容易超时。
    貌似这类N-sum问题的解法还是双指针比较好啊,leetcode讨论区有一个双指针通解的,N>=2以上采用递归降阶,速度很快推荐大家都去看看。
    2018-11-01
    3
  • 缪文@场景鹿
    这个三元组的去重有点难,我是将三元组排序后将整个三元组放到Set中去重的。
    2018-12-25
    2
  • 这个题有一个非常难理解的地方需要一个小学的数学知识来理解一下:
    a+b+c=0;
    a=-b-c
    b=-a-c
    c=-a-b
    2018-12-14
    2
  • Li ²⁰¹⁸
    问下老师,为什么最后一个解法 append((a,b,c))(返回三元组) 而不是 append([a,b,c]) (返回一个list)
    2018-11-08
    2
  • 寒风
    第三种方法,快排也有时间复杂度,没算进去啊。。。

    作者回复: 快排 nlogn,小于 n×n ,另外也不是嵌套运算,所以只要算 n×n

    2018-11-06
    1
    2
  • 王磊
    3sum是否可以一层遍历后,然后调用之前的2sum,是否实现更简单?复杂度也是N平方

    作者回复: 可以的。注意元素盼重的问题。

    2018-10-27
    2
  • 民工597
    不能用set吧,这样可能出现2,2,4这种

    作者回复: 代码里需要进行判重的技术处理。

    2019-10-08
    1
  • 小永
    java实现,供参考;Arrays.sort在jdk里使用了归并排序、快速排序、插入排序的组合策略(根据元素的多寡来设置的门限),会在循环外层浪费一定时间,但不影响大O的复杂度;提交力扣会有概率性地被判定为超时的情况,比如输入nums为{0, 0, 0}的时候也会做几次空跑的循环,应该还有优化的空间。

    public List<List<Integer>> threeSum(int[] nums) {
            Set<List<Integer>> result = new HashSet<>();

            //排序需要(Arrays.asList对基本类型的数组int[]无法准确转化为期望的list)
            List<Integer> copy = new ArrayList<Integer>() {{
                for (int num : nums) this.add(num);
            }};
            copy.sort(Comparator.comparing(Integer::intValue));

            Set<Integer> cSet;//预期的c值
            loop1:
            for (int i = 0; i < copy.size(); i++) {
                int a = copy.get(i);
                //加速(与上一个值相等,则上一轮已经找到过相同解法)
                if (i > 0 && a == copy.get(i - 1)) continue loop1;
                cSet = new HashSet<>();
                loop2:
                for (int j = i + 1; j < copy.size(); j++) {
                    int b = copy.get(j);
                    if (!cSet.contains(b)) {
                        cSet.add(-(a + b));//记录本轮的解法预期的c值,c值在后续的loop2循环中命中时说明此解存在
                    } else {
                        //因为copy是有序的,a, -(a + b), b也将呈有序排列(此轮的b就是上轮的c值),所以可以用set来进行结果去重
                        result.add(Arrays.asList(a, -(a + b), b));
                    }
                }
            }
            return new ArrayList<>(result);
        }
    2019-07-28
    1
  • 一梦如是
    第一种办法在leetcode上没有通过测试啊
    2019-02-11
    1
    1
  • 雷朝建
    谢谢老师, 解决了我一直以来的困惑。
    这道题我在leetcode上面提交了10次, 最后一次通过是用了最后一种办法, 即left和right不断逼近的方法。 其余的办法一律是: 超出时间限制(使用JS实现)。
    我想破脑袋就是无法解决, 结果一看视频试了试, 就成功了。那种感觉真爽。

    作者回复: 👍🏻👍🏻👍🏻

    2019-01-07
    1
  • 王磊
    以来2sum的3sum实现,已经在leetcode上通过。

    class Solution(object):
        def threeSum(self, nums):
            nums.sort()
            res = []
            for i, num in enumerate(nums):
                if i > 0 and nums[i] == nums[i-1]:
                    continue
                    
                new_nums = nums[i+1:]
                two_sums = self.twoSum(new_nums, -num)
                for two_sum in two_sums:
                    res.append([num, new_nums[two_sum[0]], new_nums[two_sum[1]]])
                             
            return res
                
            
        def twoSum(self, nums, target):
            d = {}
            res = []
            hit = False
            for i, num in enumerate(nums):
                if i > 1 and nums[i] == nums[i-1] and hit:
                    continue
                if num in d:
                    res.append([d[num], i])
                    hit = True
                else:
                    d[target - num] = i
                    hit = False
            return res
    2018-10-28
    1
  • 循环破解java版本显示超时,代码如下。
    public List<List<Integer>> threeSum(int[] nums) {
            HashSet<List<Integer>> set = new HashSet<>();
            for (int i = 0; i < nums.length; i++) {
                for (int j = i + 1; j < nums.length; j++) {
                    for (int k = j + 1; k < nums.length; k++) {
                        if (nums[i] + nums[j] + nums[k] == 0) {
                            Integer[] n = new Integer[]{nums[i], nums[j], nums[k]};
                            Arrays.sort(n);
                            set.add(Arrays.asList(n));
                        }
                    }
                }
            }
            return new ArrayList<>(set);
        }
    2019-11-16
  • 真飞鸟
    自己试了下以及看了下评论,好像的确是没办法达到不打乱原数组来达到去重的效果
    2019-10-28
  • Aliliin
    PHP 模仿老师讲解的方法实现:

    function threeSum($nums)
        {
            $len = count($nums);
            if ($len < 3){
                 return [];
            }
            if ($len == 3) {
                if (array_sum($nums) == 0) {
                    return [$nums];
                }
            }
            $res = [];
            sort($nums);
            for ($i = 0; $i < $len - 3; $i++) {
                if ($i > 0 && $nums[$i] == $nums[$i - 1]) {
                    continue;
                }
                $l = $i + 1;
                $r = $len - 1;
                while ($l < $r) {
                    $s = $nums[$i] + $nums[$l] + $nums[$r];
                    if ($s < 0) {
                        $l += 1;
                    } elseif ($s > 0) {
                        $r -= 1;
                    } else {
                        $res[] = [$nums[$i], $nums[$l], $nums[$r]];
                        while ($l < $r && $nums[$l] == $nums[$l + 1]) {
                            $l += 1;
                        }
                        while ($l < $r && $nums[$r] == $nums[$r - 1]) {
                            $r -= 1;
                        }
                        $l += 1;
                        $r -= 1;
                    }
                }
            }
            return $res;
        }

    作者回复: Good!

    2019-10-20
  • Mr.周
    第二种用set,时间复杂度为o(n2),但是在letcode上,还是无法通过。
    2019-10-18
  • Beck
    老师是用什么语言呢?
    2019-10-17
收起评论
看过的人还看
趣谈网络协议

刘超  网易研究院云计算技术部首席架构师

51讲 | 39744 人已学习

拼团 ¥79 原价 ¥99
数据结构与算法之美

王争  前Google工程师

75讲 | 72108 人已学习

拼团 ¥79 原价 ¥99
左耳听风

陈皓  网名“左耳朵耗子”,资深技术专家,骨灰级程序员

108讲 | 40620 人已学习

拼团 ¥199 原价 ¥299
Java核心技术面试精讲

杨晓峰  前Oracle首席工程师

43讲 | 43408 人已学习

拼团 ¥79 原价 ¥99