经典双指针算法试题(二)

简介: 经典双指针算法试题(二)

一、有效三角形的个数


1、题目讲解

0b37a62bd40f4f7d8b158dbf2465eb5f.png

2、讲解算法原理

6b55168b0d904840b68fb547aece02e1.png

c80305854e69457bbda07014b44d9b2a.png

3、代码实现

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



二、查找总价格为目标值的两个商品


1、题目讲解

d8073d6e76bd4d5d9599fd118845158d.png

2、讲解算法原理

b76b84f58f9e4d9db0860b1bfc7eed52.png

3、代码实现

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        int left=0,right=price.size()-1;
        while(left<right)
        {
            int sum=price[left]+price[right];
            if(sum>target)  right--;
            else if(sum< target) left++;
            else break;
        }
        return  {price[left],price[right]};  
    }
};



三、三数求和


1、题目讲解

8b3874c237e64e92a4a3bd6756f7cb47.png

59e7869e1ac745a7be22fdb30829fbf7.png

2、讲解算法原理

9c7b300a10954b6a966ba3e3ffab42bd.png

8178adbe7aa04e2597c1db9d5f533a85.png

3、代码实现

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int>> ret;
        int n=nums.size();
        for(int i=0;i<n-2;)
        {
            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]});
                    left++;
                    right--;
                    while(left<right && nums[left]==nums[left-1]) left++;
                    while(left<right && nums[right]==nums[right+1]) right--;
                }
            }
            i++;
            while(i<n && nums[i]==nums[i-1]) i++;
        }
        return ret;
    }
}; 



四、四数求和


1、题目讲解

0cfc547f9f064cf68404d57e22fe2eda.png

2、讲解算法原理

41f8d88f380e4c8686de68ebf6234703.png

3、代码实现

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


目录
相关文章
|
1月前
|
算法 前端开发 Java
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
这篇文章总结了单链表的常见面试题,并提供了详细的问题分析、思路分析以及Java代码实现,包括求单链表中有效节点的个数、查找单链表中的倒数第k个节点、单链表的反转以及从尾到头打印单链表等题目。
32 1
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
|
5月前
|
算法
双指针算法
双指针算法
31 2
|
2月前
|
算法 索引 容器
双指针算法详解
本文介绍了双指针算法及其应用。双指针算法是在数组或字符串中常用的高效技术,通过维护两个指针遍历数据结构以解决特定问题。根据指针移动方向,可分为同向双指针、相向双指针和快慢指针。同向双指针如移动零和复写零问题;快慢指针如快乐数问题;相向双指针如盛水最多的容器、有效三角形数量及多数之和等问题。通过合理运用双指针技巧,可简化代码并提高效率。
60 4
双指针算法详解
|
1月前
|
算法 C++
【算法】双指针+二分(C/C++
【算法】双指针+二分(C/C++
|
1月前
|
搜索推荐 C语言 C++
【C语言】指针篇-精通库中的快速排序算法:巧妙掌握技巧(4/5)
【C语言】指针篇-精通库中的快速排序算法:巧妙掌握技巧(4/5)
|
3月前
|
算法 容器
【算法】双指针
【算法】双指针
|
3月前
|
算法 C++ 容器
【C++算法】双指针
【C++算法】双指针
|
25天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
9天前
|
算法 数据挖掘 数据安全/隐私保护
基于FCM模糊聚类算法的图像分割matlab仿真
本项目展示了基于模糊C均值(FCM)算法的图像分割技术。算法运行效果良好,无水印。使用MATLAB 2022a开发,提供完整代码及中文注释,附带操作步骤视频。FCM算法通过隶属度矩阵和聚类中心矩阵实现图像分割,适用于灰度和彩色图像,广泛应用于医学影像、遥感图像等领域。