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

三数之和

时间:2023-05-02 22:11:25浏览次数:28  
标签:right nums int 三数 三元组 result left

题目:

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

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

示例:

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

满足要求的三元组集合为: [ [-1, 0, 1], [-1, -1, 2] ]

 

需要注意的点:

1、用双指针的解法,双指针解法使用前需要排序

2、注意去重的情况

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(),nums.end());//数组先排序
        for(int i=0;i<nums.size();i++)
        {
            if(nums[i]>0)//最小的数大于0则不存在等于0的情况
            {
                return result;
            }

            //对第一个数去重,向后取值
            if(i>0 && nums[i]==nums[i-1])
            {
                continue;
            }

            int left=i+1;
            int right=nums.size()-1;
            while(right>left)
            {
                int sum=nums[i]+nums[left]+nums[right];
                if(sum>0)right--;
                else if(sum<0)left++;
                else{
                result.push_back(vector<int>{nums[i],nums[left],nums[right]});

                //第二个数与第三个数去重
                while(right>left && nums[left]==nums[left+1])left++;
                while(right>left && nums[right]==nums[right-1])right--;
                
                //找到答案,双指针同时收缩
                left++;
                right--;

                }

            }
 
        }
        return result;

    }
};

 

标签:right,nums,int,三数,三元组,result,left
From: https://www.cnblogs.com/gaishuobulao/p/17368395.html

相关文章

  • 最接近的三数之和
    最接近的三数之和题目描述题解暴力解法即是三重循环,时间复杂度为\(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)......
  • #yyds干货盘点# LeetCode程序员面试金典:三数之和
    题目:给你一个整数数组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]输......
  • 【230402-6】从集合{2,4,5,6,7,8}中选三数,使三数和可被3整除,有多少种取法?
    ......
  • 代码随想录Day7-Leetcode454. 四数相加 II,383. 赎金信 ,15. 三数之和 ,18. 四数之和
    454.四数相加II这个第一时间没想出来怎么做的;后面看了题解才发现可以两两分组;绝了/***@param{number[]}nums1*@param{number[]}nums2*@param{number[......
  • LeetCode15. 三数之和
    题目描述:给你一个整数数组nums,判断是否存在三元组[nums[i],nums[j],nums[k]]满足i!=j、i!=k且j!=k,同时还满足nums[i]+nums[j]+nums[k]==0。请你......
  • LeetCode 16. 最接近的三数之和
    classSolution{public:intthreeSumClosest(vector<int>&nums,inttarget){intn=nums.size();pair<int,int>res(INT_MAX,0);//分别存储差......
  • LeetCode 15. 三数之和
    classSolution{public:vector<vector<int>>threeSum(vector<int>&nums){vector<vector<int>>res;sort(nums.begin(),nums.end());......