栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

LeetCode高频题15:三数之和

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

LeetCode高频题15:三数之和

LeetCode高频题15:三数之和

提示:本题是系列LeetCode的150道高频题,你未来遇到的互联网大厂的笔试和面试考题,基本都是从这上面改编而来的题目
互联网大厂们在公司养了一大批ACM竞赛的大佬们,吃完饭就是设计考题,然后去考应聘人员,你要做的就是学基础树结构与算法,然后打通任督二脉,以应对波云诡谲的大厂笔试面试题!
你要是不扎实学习数据结构与算法,好好动手手撕代码,锻炼解题能力,你可能会在笔试面试过程中,连题目都看不懂!比如华为,字节啥的,足够让你读不懂题

本题的类似基础知识:
【1】LeetCode高频题1:两数之和


文章目录
  • LeetCode高频题15:三数之和
    • @[TOC](文章目录)
  • 题目
  • 一、审题
  • 本题类似的基础知识:两数之和,一定要看懂了
  • 本题三数之和的基础:两数之和,在数组arr中:找到所有加起来为k的不重复的a与b【二元组】
  • 累加和可以为k=target,不一定是0这个特定的数
  • 总结
题目

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。

注意:答案中不可以包含重复的三元组。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


一、审题

示例 1:

输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
示例 2:

输入:nums = []
输出:[]
示例 3:

输入:nums = [0]
输出:[]
不足3个,肯定不行的,最少3元素

提示:

0 <= nums.length <= 3000
-105 <= nums[i] <= 105


本题类似的基础知识:两数之和,一定要看懂了

【1】LeetCode高频题1:两数之和
这里面是给定a和target,在数组中找一个数b,让b+a=target,但是这题不是咱们今天要的两数之和


本题三数之和的基础:两数之和,在数组arr中:找到所有加起来为k的不重复的a与b【二元组】

咱们的两数之和是这样的:

(0)咱们先给arr排序
(2)然后双指针指向0和N-1
(3)看看[L]+[R]与k的大小关系
如果:[L]+[R] 如果:[L]+[R]>k,说明R太大了,需要R–
如果:[L]+[R]=k,说明LR巧了加起来为k,收集LR作为一个二元组答案,然后需要R–或者L++,随意
(4)收集答案时,要保证L数字与L-1之前的数不一样的,否则就重复了

比如:下图arr,k=3
(1)最开始-1+4=3,由于i=0,-1位置没有数,可以收集答案(-1,4),然后L++
(2)你会发现-1+4=3,可以收集答案???不一定哦!L和L-1处俩数相等,你再收集(-1,4)就重复了呗……所以不收集

(3)然后你继续L++,++,到了4那个地方
你发现4+4=8>k=3,R–,R–,R–,R–

(4)已然L=R了,不行了

没得玩
反就是L与L-1不同才可能是答案,懂?

手撕代码问题不大吧?

        //继续优化
        //复习:二元组和为k的思想,双指针
        public List> twoTupleSumk(int[] arr,int l, int r, int k){
            //保证arr俩数以上哦!
            //(0)咱们先给arr排序
            Arrays.sort(arr);
            //(2)然后双指针指向0和N-1
            int L = l;
            int R = r;
            List> ans = new ArrayList<>();//结果(a,b)(c,d)
            //(3)看看[L]+[R]与k的大小关系
            while (L < R){//等时不行的,俩数呢
                List two = new ArrayList<>();//中途可能收集到一个ab二元组
                //如果:[L]+[R]=k,说明LR巧了加起来为k,收集LR作为一个二元组答案,然后需要R--或者L++,随意
                //(4)收集答案时,**要保证L数字与L-1之前的数不一样的**,否则就重复了
                int tmp = arr[L] + arr[R];
                if (tmp == k && (L == l ? true : arr[L] != arr[L - 1])){
                    //收集答案
                    two.add(arr[L]);
                    two.add(arr[R]);
                    ans.add(two);
                    L++;
                }else if (tmp < k) L++;//如果:[L]+[R]k,说明R太大了,需要R--
            }
            return ans;
        }

测试一把:

    public static void test(){
        int[] arr = {3,0,-2,-1,1,2};
        Solution solution = new Solution();
        int k = 0;
        List> res = solution.twoTupleSumk(arr, 0, arr.length - 1, k);
        for(List lists:res){
            for(Integer i:lists) System.out.print(i +" ");
            System.out.println();
        }
        
    }

    public static void main(String[] args) {
        test();
    }

问题不大:

-2 2 
-1 1 

来个重复的:

int[] arr = {3,0,-2,-1,-1,-1,1,2};

还是这个结果:
-2 2 
-1 1 

有了两数之和,就可以拿来做三数之和


累加和可以为k=target,不一定是0这个特定的数

(0)还是排序一波arr
思想非常非常非常非常简单:
你要求三元组abc的和为k
(1)那么我让arr的0–N-3的每一个位置p,都做一次a,看看p+1–N-1上有没有可能找到一个二元组bc来,
也就是咱们调用上面那个twoTupleSumk函数,去求它上面累加和为**k0=k-arr[p]**这个目标下的二元组bc来
跟a组装为一个三元组,就是咱们要的结果

比如上图中,k=5,p来到-3,显然,-3做开头a的话,
后续整个范围上有没有一个让二元组bc累加和为k0=k-arr[p]=5-(-3)=8的呢?
有谁为累加和8?拿过来跟前面的-3拼一起就是一个结果

注意,p收集过答案了
如果p++之后,数字还是和前面的数一样,那跳过,不需要找a相同的情况
也是为了避免重复,懂?
比如下面第一个-3,已经让k=3时,求到了答案
第二个-3就没必要重复求了呗!

手撕代码问题不大吧?

        你要求三元组abc的和为k//思想非常非常非常非常简单:
        public List> threeTupleSumk(int[] nums, int k) {
            //进来一定有3个以上的数

            //(0)还是排序一波arr
            Arrays.sort(nums);
            //(1)那么我让arr的0--N-3的每一个位置p,都做一次a,看看p+1--N-1上有没有可能找到一个二元组bc来,
            //也就是咱们调用上面那个twoTupleSumk函数,去求它上面累加和为**k0=k-arr[p]**这个目标下的二元组bc来
            //跟a组装为一个三元组,就是咱们要的结果
            List> ans = new ArrayList<>();
            int i = 0;
            int N = nums.length;
            while (i <= N - 3){
                //需要i和i-1是不相同的数
                if (i == 0 || nums[i] != nums[i - 1]){
                    List> two = twoTupleSumk(nums, i + 1, N - 1, k - nums[i]);
                    //k0=k-[i]
                    for(List list:two){
                        List three = new ArrayList<>();//可能会找到
                        //找到了挨个加入three
                        three.add(nums[i]);//a
                        three.add(list.get(0));//b
                        three.add(list.get(1));//c
                        ans.add(three);//加入结果
                    }
                }
                i++;//每个i做一次开头看看
            }

            return ans;
        }

        //leetCode15
        public List> threeSum(int[] nums) {
            if (nums == null || nums.length < 3) return new ArrayList<>();

            return threeTupleSumk(nums, 0);//但是leet是要求k=0的情况
        }

关注两个点,收集结果前three要清零
还有保证i-1和i位置数不相同才行

测试:

    public static void test(){
        int[] arr = {3,0,-2,-1,-1,-1,1,2};
        Solution solution = new Solution();
        int k = 0;
        List> res = solution.twoTupleSumk(arr, 0, arr.length - 1, k);
        for(List lists:res){
            for(Integer i:lists) System.out.print(i +" ");
            System.out.println();
        }

        System.out.println();
        res = solution.threeSum(arr);
        for(List lists:res){
            for(Integer i:lists) System.out.print(i +" ");
            System.out.println();
        }
        
    }

    public static void main(String[] args) {
        test();
    }

问题不大:

-2 2 
-1 1 

-2 -1 3 
-2 0 2 
-1 -1 2 
-1 0 1

很容易的
LeetCode测试:


问题不大!
上速度慢,一方面因为
//Arrays.sort(arr);//如果是三元组那排好序了就不要再浪费时间了

改了之后可能就快点


总结

提示:重要经验:

1)二元组的和为k的求法,排序双指针,非常经典的做法了,不重复的
2)三元组的和为k的求法,利用二元组二元组的和为k-arr[i]的求法,让每一个i做一次三元组的排头a,再用二元组求bc,组合起来,保证i不等于i-1位置的数,就是不重复的
3)笔试求AC,可以不考虑空间复杂度,但是面试既要考虑时间复杂度最优,也要考虑空间复杂度最优。

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/980991.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号