首页 > 其他分享 >LC15. 三数之和

LC15. 三数之和

时间:2023-05-21 14:33:28浏览次数:43  
标签:right nums ++ 三数 数值 三元组 LC15 left

 题目来源于力扣题库,题目链接:LC15. 三数之和

Q:给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

示例1:

输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解释:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意,输出的顺序和三元组的顺序并不重要。

示例2:

输入:nums = [0,1,1]
输出:[]
解释:唯一可能的三元组和不为 0 。

示例3:

输入:nums = [0,0,0]
输出:[[0,0,0]]
解释:唯一可能的三元组和为 0 。

提示:

  • 3 <= nums.length <= 3000
  • -105 <= nums[i] <= 105

A:思路:题目给出的要求是从一个整数数组中不断找到三数之和为0的三元组,条件是这三个数所对应的索引均不相同,且结果集中不能存在重复的三元组。

  拿到该题,最容易想到的是用暴力解法,三个for循环开干。但是,通过对时间复杂度的一个分析,发现这样是行不通的,随后,曾经做过的两数之和的思路可能突然间给了自己一个思路,即用哈希表来做。事实上,利用哈希表是可以做出来的,但是过程有些过于复杂,尤其是对于去重问题,且时间复杂度也不低。

  最后,只能去求助于双指针,双指针的主要思路是先对数组进行排序,然后利用一层for循环去的固定一个数值nums[i](i∈[0, nums.length - 1]),随后构建两个指针left和right,初始化使得left = i + 1,right = nums.length - 1(left指向i的下一个数值,right指向nums的最后一个数值),在while(left < right)循环中,去使得left和right不断的靠近,即left++,right--。由于数组是经过排序的,所以是递增的,当遇到nums[i] + nums[left] + nums[right] > 0时,说明和太大了,那么我们就让right指针往前移动right--,使得和变小一点;同理如果遇到nums[i] + nums[left] + nums[right] < 0时,那么说明总和太小了,我们就让left指针往后移动left++,使得和变大一点。这样不断的去找到满足nums[i] + nums[left] + nums[right] == 0 的三个数值,且它们的下标是不重复的,但是还有一个问题就是,如何解决结果集中重复的三元组组合问题呢?

  这里便涉及到了关键的操作:去重,如何去重,举例来讲,例如有一数组: {-1, -1, -1, 2},我们可以发现,里面的一个组合{-1, -1, 2}是满足题意的,但是如果不进行去重操作,那么就会出现重复的三元组{-1, -1, 2}。解决该问题的一个关键思路是如果当前for循环中需要固定的数值num[i] == nums[i-1]时,就直接continue,跳过此轮for循环。为什么要这样?因为nums[i - 1]已经被我们用过了,且其后面对应的一些可以满足组合的数值也都用过了,均加入了结果集中了。那么如果现在我们还使用与nums[i-1]相同数值的nums[i],并且同样的往后找到满足的组合,那么必定会出现重复的三元组,简单来说就是又以同样的数值nums[i]去找了一遍满足题意的组合。

  故我们得知去重的第一个条件就是在for循环中,如果遇到i > 0 && nums[i] == nums[i - 1],则直接continue,开启下一轮for循环。但是现在似乎只完成了一次去重,还有二次去重,例如nums:{0, -1, -1, -1, -1, -1, -1, 1, 1, 1, 1, 1},我们可以很容易的找到满足题意的三元组{0,-1,1},但是此时会出现往后的{0,-1,1}还是满足的,显然这是不符合题意的,虽然它们三个下标不同,但是三元组是重复的。其实这个问题其实很好解决,当我们发现nums[left] == nums[left + 1] 时,就让left指针不断的往后移动,即left++,跳过那些重复的数值;同理当我们发现nums[right] == nums[right - 1]时,就让right指针不断的往前移动,即right--即可,至此,二次去重问题便解决了。

  最后要说的是,每当找到一组满足题意的三元组加入到结果集后,且二次去重完成后,还要进行一次left++和right--,使得left和right指针指向下一个需要判断的三元组。

  以下是Java代码,仅供参考:

 

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();

        int n = nums.length;

        Arrays.sort(nums); // 排序

        for(int i = 0; i < n; i++){
            if(nums[i] > 0) return res; // 排序后的第一个数值如果已经大于0,则直接返回res

            if(i > 0 && nums[i] == nums[i - 1]) continue; // 一次去重

            int left = i + 1; // 对于每一次的i,更新left
            int right = n - 1; // 对于每一次的i,更新right

            while(left < right){
                int sum = nums[i] + nums[left] + nums[right];

                if(sum < 0){ // 总和太小了,使left往后挪一挪
                    ++left;
                }else if(sum > 0){ // 总和太大了,使right往前挪一挪
                    --right;
                }else{
                    res.add(Arrays.asList(nums[i], nums[left], nums[right])); // 收集结果
                    while(left < right && nums[left] == nums[left + 1]) ++left; // 二次去重
                    while(left < right && nums[right] == nums[right - 1]) --right; // 二次去重

                    ++left; // 指向下一个待判断的数值
                    --right; // 指向下一个待判断的数值
                }
            }
        }
        return res;
    }
}

 

标签:right,nums,++,三数,数值,三元组,LC15,left
From: https://www.cnblogs.com/fxy0715/p/17418493.html

相关文章

  • 西门子PLC1500大型程序fanuc机器人汽车焊装 包 西门子PLC1500大型程序fanuc机器人汽
    西门子PLC1500大型程序fanuc机器人汽车焊装包西门子PLC1500大型程序fanuc机器人汽车焊装包括1台西门子1500PLC程序,2台触摸屏TP1500程序9个智能远程终端ET200SPProfinet连接15个Festo智能模块Profinet通讯10台Fanuc发那科机器人Profinet通讯3台G120变频器Profinet通讯2台智......
  • 代码随想录算法训练营第七天|454. 四数相加 II、383. 赎金信、15. 三数之和、18. 四数
    【参考链接】454.四数相加II【注意】1.a+b作为key,出现次数作为value,0-(c+d)有没有在map集合里出现过,出现的次数做统计。遍历两个数组时间复杂度为O(n2)。【代码】1classSolution(object):2deffourSumCount(self,nums1,nums2,nums3,nums4):3"""......
  • 代码随想录算法训练营第7天 | ● 454.四数相加II ● 383. 赎金信 ● 15. 三数之和
     第三章 哈希表part02  今日任务  ●  454.四数相加II ●  383. 赎金信 ●  15. 三数之和 ●  18. 四数之和 ●  总结    详细布置   454.四数相加II  建议:本题是 使用map 巧妙解决的问题,好好体会一下 哈希法 如何提高程序......
  • 西门子PLC1500大型程序 西门子PLC1500大型程序fanuc机
    西门子PLC1500大型程序西门子PLC1500大型程序fanuc机器人焊装包括1台西门子1500PLC程序,2台触摸屏TP1500程序9个智能远程终端ET200SPProfinet连接15个Festo智能模块Profinet通讯10台Fanuc发那科机器人Profinet通讯3台G120变频器Profinet通讯2台智能电能管理仪表PAC32004个GRAPH顺......
  • LeetCode 15. 三数之和
    题目链接:LeetCode15.三数之和题意:在给定的数组中,找出三个数(三个数不重复)使得他们相加的和为0,同时答案中不能有重复的答案解题思路:完整代码如下://双指针做法首先要有序//解法一最优解,双指针+排序functhreeSum(nums[]int)[][]int{varres[][]intsor......
  • 三数之和
    题目:给你一个包含n个整数的数组 nums,判断 nums 中是否存在三个元素a,b,c,使得 a+b+c=0?请你找出所有满足条件且不重复的三元组。注意: 答案中不可以包含重复的三元组。示例:给定数组nums=[-1,0,1,2,-1,-4],满足要求的三元组集合为:[[-1,0,1],[-1,-1,2......
  • 最接近的三数之和
    最接近的三数之和题目描述题解暴力解法即是三重循环,时间复杂度为\(O(n^3)\)。但是,这种多个数字求和的题目都可以通过双指针的方法降低一层循环。首先我们枚举元素a,那么对于剩下的两个元素b和c,我们希望它们的和能够接近target-a。但是若要利用双指针,则需要一点预处理过程,即对数......
  • 15.三数之和——学习笔记
    题目:给你一个整数数组nums,判断是否存在三元组[nums[i],nums[j],nums[k]]满足i!=j、i!=k且j!=k,同时还满足nums[i]+nums[j]+nums[k]==0。请你返回所有和为0且不重复的三元组。注意:答案中不可以包含重复的三元组。示例1:输入:nums=[-1,0,1,2,-1,-4]输......
  • 15. 三数之和
    题目链接:15.三数之和方法:排序+相向双指针解题思路由题意可知,排序不影响结果,非递减排序之后3数之和满足单调性,即\(x<x1\)||\(y<y1\)||\(z<z1\),\(f(x,y,z)<f(x1,y1,z1)\);现在枚举\(x\)下标\(0<=i<=n-2\),在\([x+1,n-1]\)中选择\(y\),\(z\)的下标......
  • #yyds干货盘点# LeetCode程序员面试金典:最接近的三数之和
    题目:给你一个长度为n的整数数组 nums 和一个目标值 target。请你从nums中选出三个整数,使它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在恰好一个解。 示例1:输入:nums=[-1,2,1,-4],target=1输出:2解释:与target最接近的和是2(-1+2+1=2)......