LeetCode高频题15：三数之和

之和"/>

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）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、审题

示例 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]<k，说明L太小了，需要L++
如果：[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<List<Integer>> twoTupleSumk(int[] arr,int l, int r, int k){//保证arr俩数以上哦！//（0）咱们先给arr排序Arrays.sort(arr);//（2）然后双指针指向0和N-1int L = l;int R = r;List<List<Integer>> ans = new ArrayList<>();//结果(a,b)(c,d)//（3）看看[L]+[R]与k的大小关系while (L < R){//等时不行的，俩数呢List<Integer> 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，说明L太小了，需要L++else R--;//如果：[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<List<Integer>> res = solution.twoTupleSumk(arr, 0, arr.length - 1, k);for(List<Integer> 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<List<Integer>> threeTupleSumk(int[] nums, int k) {//进来一定有3个以上的数//（0）还是排序一波arrArrays.sort(nums);//（1）那么我让arr的0--N-3的每一个位置p，都做一次a，看看p+1--N-1上有没有可能找到一个二元组bc来，//也就是咱们调用上面那个twoTupleSumk函数，去求它上面累加和为**k0=k-arr[p]**这个目标下的二元组bc来//跟a组装为一个三元组，就是咱们要的结果List<List<Integer>> 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<List<Integer>> two = twoTupleSumk(nums, i + 1, N - 1, k - nums[i]);//k0=k-[i]for(List<Integer> list:two){List<Integer> three = new ArrayList<>();//可能会找到//找到了挨个加入threethree.add(nums[i]);//athree.add(list.get(0));//bthree.add(list.get(1));//cans.add(three);//加入结果}}i++;//每个i做一次开头看看}return ans;}//leetCode15public List<List<Integer>> 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<List<Integer>> res = solution.twoTupleSumk(arr, 0, arr.length - 1, k);for(List<Integer> lists:res){for(Integer i:lists) System.out.print(i +" ");System.out.println();}System.out.println();res = solution.threeSum(arr);for(List<Integer> 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，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。