【优选算法】7----三数之和

用户11456817

发布于 2025-01-24 11:46:46

1220

文章被收录于专栏：学习学习

来了来了，他来了，又是学习算法的一天~

今天的嘉宾是中等难度的算法题----三数之和！

------------------------------------------begin------------------------------------

题目解析：

哇趣！又是给了一个数组，又是需要我们在一个数组中进行操作，但这次不是二元那么简单了，而

是三元~

讲解算法原理：

方法一：肯定还是暴力解法啦，直接三个for循环编译，时间复杂度直接爆炸，包不通过的~（所以

不推荐）

方法二：基于暴力算法，我们才可以进行优化算法，还是需要我们的老朋友left和right指针来进行

编译，同样我们需要多加一个对象来固定一个数，题目要求三数相加为0，所以我们可以定义一个

target来取所固定的相反数来与left和right位置的值的和来进行比较，判断~

编写代码：

class Solution 
{
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        vector<vector<int>>ret;
        sort(nums.begin(),nums.end());
        int n=nums.size();
        for(int i=0;i<n;)
        {
            if(nums[i]>0)
            {
                break;
            }
            int left=i+1,right=n-1,target=-nums[i];
            while(left<right)
            {
                int sum=nums[left]+nums[right];
                if(sum>target)
                {
                    right--;
                }
                else if(sum<target)
                {
                    left++;
                }
                else
                {
                    ret.push_back({nums[i],nums[left],nums[right]});
                    right--;
                    left++;
                    while(left<right&&nums[right]==nums[right+1])
                    {
                        right--;
                    } 
                    while(left<right&&nums[left]==nums[left-1])
                    {
                        left++;
                    }
                }
            }
            i++;
            while(i<n&&nums[i]==nums[i-1])
            {
                i++;
            }
        }
         return ret;
    }
};

题目还是有点复杂的，不过多画图还是有用的哦~

题目直达->

15. 三数之和 - 力扣（LeetCode）

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-01-24，如有侵权请联系 cloudcommunity@tencent.com 删除

原理