双指针算法·两数之和·三数之和

简介: 双指针算法·两数之和·三数之和

如题目所示,这篇文章要讲解的三道题是有很大的关联的,循循渐进逐步展开,介绍双指针算法在解决这类题时能带来的优化。

两数之和

这道题比较简单,也是带入这种题型不错的选择,如题目所说,提供的数组已经是升序,使用暴力解法将所有的两数组合全部遍历一遍,这种解法的时间复杂度为O(N2),而且题目所提供的升序数组也没有用到,素以我们可以借助升序来寻找跟好的算法。

双指针你一定会想到,因为是升序,我们可以用两个指针left和right分别指向数组首位置和末位置,这样就可以知道最大元素和最小元素的和,如果和是大于目标值,就左移right,此时得到的目标值就会减小(因为是升序嘛),如果小于目标值,那就右移left,这样的道德目标值就会变大,这样只需要遍历一遍就可以债哦哦到结果。

以下是C++解法

vector<int> twoSum(vector<int>& price, int target) {
  int i=0,j=price.size()-1;
    vector<int> a;//偷懒了i->left j->right
    while(i!=j)
    {
        int sum=price[i]+price[j];
        if(sum<target)
        {
            i++;
        }
        if(sum>target)
        {
            j--;
        }
        if(sum==target)
        {
            break;
        }
    }
    a.push_back(price[i]);
    a.push_back(price[j]);
    return a;
}

三数之和

有了前一道题的衬托,我们就可以很轻松的想出这道题的解法,首先还是要介绍暴力解法,三层for循环,遍历出所有符合条件的三元组,但是这道题有很难搞的地方就是不可以包含重复的三元组,所以我们找出所有的三元组之后还需要进行去重操作。

先思考思考如何使用双指针算法思想进行解决,对于第一道题目,有着很重要的条件,那就是升序数组,我们可以找出规律从而简化以减少遍历次数,减小时间复杂度。

所以我们要先将数组排序,返回值类型为二维数组,我们提前构造一个二维数组作为返回值。

此时数组已经是一个升序数组了,我们的目标是找到三个数是他们的和等于0,换一种思路就是找到两个数,使他们的和等于第三个数的负数,这样就回归到两数之和了,首先我们要先锁定一个数,作为第三个数,在剩下的数中找到两个使它们的和等于锁定的数的负数即可,找两个数的操作和第一题的思路一模一样。

如何去重呢?

这是一个比较麻烦的问题。

在找到一组符合要求的值之后,判断left后边的和前边的值是否和已经记录过的相同,如果相同的话,那就跳过相同的数,就可以实现去重操作。不要忘记咯,我们选择的目标值也是要跳过相同的元素(就是目标值也是不同的),这样就切切实实实现了去重操作。

举例说明:

在锁定1之后,后边的1也要全部跳过,在left为-1right为0时,符合条件,但是为了去重,right要跳过所有的1,left要跳过所有的-1,即去重操作。要注意的是,在left前移和right后移的过程中,left保持恒小于right。

这道题目还要注意的点就是返回的对象为二维数组,在打印时可以使用两层for循环。

代码如下

class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums)
{
    vector<vector<int>> a;
    sort(nums.begin(), nums.end());
    int size = nums.size() - 1;
    for (int i = size; i >= 0; )
    {
        if (nums[i] < 0)
        {
            break;
        }
        int target = -nums[i];
        int right = i - 1;
        int left = 0;
        while (left < right)
        {
            if (nums[right] + nums[left] > target)right--;
            else if (nums[right] + nums[left] < target)left++;
            else {//此时我们找到了符合条件的值
                a.push_back({ nums[i],nums[right],nums[left] });//直接将这个三元组插入
                left++;
                right--;
                //去重操作
                while (left < right && nums[left] == nums[left - 1])left++;
                while (left < right && nums[right] == nums[right + 1])right--;
            }
        }
        i--;
        while (i > 0 && nums[i] == nums[i + 1])
        {
            i--;
        }
    }
    for (auto i : a)
    {
        for (auto s : i)
        {
            cout << s << ' ';
        }
        cout << endl;
    }
    return a;
}
};
目录
相关文章
|
1天前
|
算法 容器
【算法】——双指针算法合集(力扣)
移动零,复写零,快乐数,盛最多水的容器,有效三角形的个数,和为s的两个数(查找总价格为目标值的两个商品 ),三数之和,四数之和
|
6月前
|
算法
双指针算法
双指针算法
40 2
|
3月前
|
算法 索引 容器
双指针算法详解
本文介绍了双指针算法及其应用。双指针算法是在数组或字符串中常用的高效技术,通过维护两个指针遍历数据结构以解决特定问题。根据指针移动方向,可分为同向双指针、相向双指针和快慢指针。同向双指针如移动零和复写零问题;快慢指针如快乐数问题;相向双指针如盛水最多的容器、有效三角形数量及多数之和等问题。通过合理运用双指针技巧,可简化代码并提高效率。
75 4
|
2月前
|
算法 C++
【算法】双指针+二分(C/C++
【算法】双指针+二分(C/C++
|
2月前
|
搜索推荐 C语言 C++
【C语言】指针篇-精通库中的快速排序算法:巧妙掌握技巧(4/5)
【C语言】指针篇-精通库中的快速排序算法:巧妙掌握技巧(4/5)
|
4月前
|
算法 容器
【算法】双指针
【算法】双指针
|
4月前
|
算法 C++ 容器
【C++算法】双指针
【C++算法】双指针
|
4月前
|
存储 算法 Java
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
49 0
|
6月前
|
算法 容器
【经典LeetCode算法题目专栏分类】【第1期】左右双指针系列:盛最多水的容器、接雨水、回文子串、三数之和
【经典LeetCode算法题目专栏分类】【第1期】左右双指针系列:盛最多水的容器、接雨水、回文子串、三数之和

热门文章

最新文章