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

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

一、有效三角形的个数


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;
    }
};


目录
相关文章
|
20天前
|
算法 前端开发 Java
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
这篇文章总结了单链表的常见面试题,并提供了详细的问题分析、思路分析以及Java代码实现,包括求单链表中有效节点的个数、查找单链表中的倒数第k个节点、单链表的反转以及从尾到头打印单链表等题目。
28 1
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
|
5月前
|
算法
双指针算法
双指针算法
30 2
|
2月前
|
算法 索引 容器
双指针算法详解
本文介绍了双指针算法及其应用。双指针算法是在数组或字符串中常用的高效技术,通过维护两个指针遍历数据结构以解决特定问题。根据指针移动方向,可分为同向双指针、相向双指针和快慢指针。同向双指针如移动零和复写零问题;快慢指针如快乐数问题;相向双指针如盛水最多的容器、有效三角形数量及多数之和等问题。通过合理运用双指针技巧,可简化代码并提高效率。
46 4
双指针算法详解
|
27天前
|
算法 C++
【算法】双指针+二分(C/C++
【算法】双指针+二分(C/C++
|
28天前
|
搜索推荐 C语言 C++
【C语言】指针篇-精通库中的快速排序算法:巧妙掌握技巧(4/5)
【C语言】指针篇-精通库中的快速排序算法:巧妙掌握技巧(4/5)
|
3月前
|
算法 容器
【算法】双指针
【算法】双指针
|
3月前
|
算法 C++ 容器
【C++算法】双指针
【C++算法】双指针
|
22天前
|
C语言
无头链表二级指针方式实现(C语言描述)
本文介绍了如何在C语言中使用二级指针实现无头链表,并提供了创建节点、插入、删除、查找、销毁链表等操作的函数实现,以及一个示例程序来演示这些操作。
19 0
|
2月前
|
存储 人工智能 C语言
C语言程序设计核心详解 第八章 指针超详细讲解_指针变量_二维数组指针_指向字符串指针
本文详细讲解了C语言中的指针,包括指针变量的定义与引用、指向数组及字符串的指针变量等。首先介绍了指针变量的基本概念和定义格式,随后通过多个示例展示了如何使用指针变量来操作普通变量、数组和字符串。文章还深入探讨了指向函数的指针变量以及指针数组的概念,并解释了空指针的意义和使用场景。通过丰富的代码示例和图形化展示,帮助读者更好地理解和掌握C语言中的指针知识。