双指针问题

BichonCode 等级 713 0 0

一、双指针之左右指针相关题目

1.1 题目要求:给定一个升序排列的整数数组,找到两个数,使它们的和等于给定的数,有且仅有一个满足条件的解,返回索引。

  • 题目分析:需要两个指针,一个指向开头,一个指向末尾,然后向中间遍历,如果指向的两个数相加正好等于target的话,直接返回两个指针的位置即可,若小于target,左指针右移一位,若大于target,右指针左移一位,以此类推直至两个指针相遇停止。
  • 题目解答:
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> res(2, -1);
        int left = 0, right = numbers.size() - 1;
        while(left < right){
            int temp = numbers[left] + numbers[right];
            if(temp > target){
                right--;
            }else if(temp < target){
                left++;
            }else{
                res[0] = left + 1;
                res[1] = right + 1;
                return res;
            }
        }
        return res;
    }
};

1.2 题目要求:给定n个整数的数组nums,nums中是否有元素a,b,c,满足a + b + c = 0? 找到数组中所有的三元组。注意:解决方案中不得包含重复的三元组。

  • 题目分析:尝试把三数和问题转化为两数和问题:同样先对数组排序,设置三个指针i,left,right,i指针指向第一个数x,则left,right要指向数组中剩余数中的两个,并且指向的两数和为-x,从而转化为两数和问题。
  • 题目解答:
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        int n = nums.size();
        if(n <= 2) return res;
        sort(nums.begin(), nums.end());
        for(int i = 0; i < n-2; i++){
            int left = i + 1, right = n - 1;
            while(left < right){
                int temp = nums[left] + nums[right];
                if(temp > -nums[i]){
                    right--;
                }else if(temp < -nums[i]){
                    left++;
                }else{
                    vector<int> tmp{nums[i], nums[left], nums[right]};
                    res.push_back(tmp);
                    left++;
                    right--;
                    while(left < right && nums[left] == nums[left - 1]) left++;
                    while(left < right && nums[right] == nums[right + 1]) right--;
                }
            }
            while(i + 1 < n -2 && nums[i] == nums[i + 1]) i++;
        }
        return res;
    }
};

1.3 题目要求:这道题让我们求最接近给定值的三数之和。

  • 题目分析:在上一道的Sum基础上又增加了些许难度,那么这道题让我们返回这个最接近于给定值的值,即我们要保证当前三数和跟给定值之间的差的绝对值最小,所以我们需要定义一个变量small用来记录差的绝对值。
  • 题目解答:
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int n = nums.size(), res = INT_MIN, small = INT_MAX;
        sort(nums.begin(), nums.end());
        for(int i = 0; i < n-2; i++){
            int left = i + 1, right = n - 1;
            while(left < right){
                int temp = nums[left] + nums[right] + nums[i];
                if(abs(temp - target) < small){
                    res = temp;
                    small = abs(temp - target);
                }
                if(temp > target){
                    right--;
                }else if(temp < target){
                    left++;
                }else{
                    return target;
                }
            }
            while(i + 1 < n -2 && nums[i] == nums[i + 1]) i++;
        }
        return res;
    }
};

1.4 题目要求:给定n个整数的数组nums,nums中是否有元素a,b,c,d 满足a + b + c + d= target? 找到数组中所有的四元组。注意:解决方案中不得包含重复的四元组。

  • 题目分析:在上一道的15. 3Sum基础上又增加了些许难度,尝试把四数和问题转化为两数和问题:同样先对数组排序,设置四个指针k,i,left,right,k指针指向第一个数,i指针指向第二个数,则left,right要指向数组中剩余数中的两个,从而转化为两数和问题。
  • 题目解答:
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> res;
        int n = nums.size();
        if(n <= 3) return res;
        sort(nums.begin(), nums.end());
        for(int k = 0; k < n-3; k++){
            for(int i = k + 1; i < n-2; i++){
                int left = i + 1, right = n - 1;
                int ret = target - nums[k] - nums[i];
                while(left < right){
                    int temp = nums[left] + nums[right];
                    if(temp > ret){
                        right--;
                    }else if(temp < ret){
                        left++;
                    }else{
                        vector<int> tmp{nums[k], nums[i], nums[left], nums[right]};
                        res.push_back(tmp);
                        left++;
                        right--;
                        while(left < right && nums[left] == nums[left - 1]) left++;
                        while(left < right && nums[right] == nums[right + 1]) right--;
                    }
                }
                while(i + 1 < n -2 && nums[i] == nums[i + 1]) i++;
            }
            while(k + 1 < n -3 && nums[k] == nums[k + 1]) k++;
        } 
        return res;
    }
};

二、双指针之快慢指针

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow = 0, fast = 0, n = nums.size();
        while(fast < n){
            if(nums[fast] != val) nums[slow++] = nums[fast];
            fast++;
        }
        return slow;
    }
};

2.1 题目要求:这道题让我们移除一个数组中和给定值相同的数字,并返回新的数组的长度。

  • 题目分析:使用slow和fast两个指针,从头部开始遍历,遍历一次fast指针前进一步,当遍历元素不满足指定的值,slow指针前进一步,这样不满足条件的整数都被移动到数组的前面。
  • 题目解答

2.2 题目要求:这道题要我们从有序数组中去除重复项。

  • 题目分析:这道题的解题思路是,我们使用快慢指针来记录遍历的坐标,最开始时两个指针都指向第2个数字,如果快指针指向的数等于慢指针的前1个数,则快指针向前走一步,如果不同,则两个指针都向前走一步,这样当快指针走完整个数组后,慢指针当前的坐标就是数组中不同数字的个数。
  • 题目解答:
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int slow = 1, fast = 1, n = nums.size();
        if(n <= 1) return n;
        while(fast < n){
            if(nums[fast] != nums[slow - 1]) nums[slow++] = nums[fast];
            fast++;
        }
        return slow;
    }
};

2.3 题目要求:这道题要我们从有序数组中去除重复项,每个数最多重复出现2次。

  • 题目分析:与上一道解题思路相似,我们使用快慢指针来记录遍历的坐标,最开始时两个指针都指向第3个数字,如果快指针指向的数等于慢指针的前2个数,则快指针向前走一步,如果不同,则两个指针都向前走一步,这样当快指针走完整个数组后,慢指针当前的坐标就是数组中不同数字的个数。
  • 题目解答:
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int slow = 2, fast = 2, n = nums.size();
        if(n <= 2) return n;
        while(fast < n){
            if(nums[fast] != nums[slow - 2]) nums[slow++] = nums[fast];
            fast++;
        }
        return slow;
    }
};

三、双指针之后序指针相关题目:

3.1题目要求:给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1中,使得 num1 成为一个有序数组。你可以假设 nums1有足够的空间(空间大小大于或等于m + n)来保存 nums2 中的元素。在 nums1 和 nums2 中初始化的元素的数量分别是 m 和 n。

  • 题目分析:算法思想是:由于合并后A数组的大小必定是m+n,所以从最后面开始往前赋值,先比较A和B中最后一个元素的大小,把较大的那个插入到m+n-1的位置上,再依次向前推。如果A中所有的元素都比B小,那么前m个还是A原来的内容,没有改变。如果A中的数组比B大的,当A循环完了,B中还有元素没加入A,直接用个循环把B中所有的元素覆盖到A剩下的位置。
  • 题目解答:
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m - 1, j = n - 1, k = m + n -1;
        while(i >= 0 && j >= 0){
            if(nums1[i] > nums2[j]) nums1[k--] = nums1[i--];
            else nums1[k--] = nums2[j--];
        }
        while(j >= 0) nums1[k--] = nums2[j--];
    }
};
收藏
评论区

相关推荐

双指针问题
一、双指针之左右指针相关题目 1.1 题目要求:给定一个升序排列的整数数组,找到两个数,使它们的和等于给定的数,有且仅有一个满足条件的解,返回索引。 题目分析:需要两个指针,一个指向开头,一个指向末尾,然后向中间遍历,如果指向的两个数相加正好等于target的话,直接返回两个指针的位置即可,若小于target,左指针右移一位,若大于target,右
02-Vue入门之数据绑定
02Vue入门之数据绑定 02Vue入门之数据绑定 2.1. 什么是双向绑定? Vue框架很核心的功能就是双向的数据绑定。 双向是指:HTML标签数据 绑定到 Vue对象,另外反方向数
前端面试系列——Vue面试题
Vue 双向绑定原理 mvvm 双向绑定,采用数据劫持结合发布者订阅者模式的方式,通过 Object.defineProperty() 来劫持各个属性的 setter、getter,在数据变动时发布消息给订阅者,触发相应的监听回调。 双
Java源码解析之LinkedList源码剖析(基于JDK1.8)
       学过数据结构的都知道双端队列(链表),没学过的也没有关系,下面我先介绍一下双端队列(链表),为什么要介绍它了,因为LinkedList本质上就是一个双端队列(链表)。 一.  双端队列(链表)的介绍 1.  如下图:双端队列(链表)中单个节点对应的结构 ![](https://oscimg.oschina.net/oscn
Java面试常被问到这道题:如何保证缓存与数据库的双写一致性?
**面试原题:如何保证缓存与数据库的双写一致性?** ![](https://oscimg.oschina.net/oscnet/up-e90c4aee3693a52b8243508bc7a22c0af71.JPEG) ### **面试官心理分析** ![](https://oscimg.oschina.net/oscnet/up-5790cf915b
java socket实现全双工通信
版权声明:本文为博主原创文章,未经博主同意不得转载。 https://blog.csdn.net/hzj9118/article/details/28419651 **单工、半双工和全双工的定义** 假设在通信过程的随意时刻,信息仅仅能由一方A传到还有一方B。则称为单工。 假设在随意时刻,信息既可由A传到B,又能由B传A。但仅仅能由一个方向上的传输存在
2020双十一淘宝领喵币&京东全名营业の自动化任务
2020双十一淘宝领喵币&京东全名营业の自动化任务 ========================= 淘宝+京东双十一活动脚本 ------------ * * * ### **不墨迹,直接放链接**:[2020双十一自动领取脚本](https://www.oschina.net/action/GoToLink?url=https%3A%2F%2Fp
12.25聚惠双旦,超低折扣
**聚惠双旦,超低折扣** 双!旦!活!动!来!袭! 如果你为错过双十一和双十二而遗憾,那千万别再错过双旦了,2020年年末,51CTO学院为新老用户送上一份“**双旦大礼**”! **视频课程全场6折!** **学习路径8折!** **会员6折!** **活动时间:12月25日-12月31日** 长按识别海报,提前将课程加购,
13_ redis数据库高可用
数据库高可用 1.1 数据库高可用说明 当数据库的主库宕机之后.如果没有高可用机制,则可能导致整个服务全部不能正常的使用. 解决策略: 双主模式(双机热备) 1.2 数据库双机热备实现 1.2.1 双机热备的说明 将2台数据库设置为双主模式.互为主从的结构.其中任意的数据库服务器既是主机.也是从机. ![在这里插入图
Beetl 3.0 有个好开头了
Beetl3.0 是新的模板引擎,有很多特性和优化,比如,支持双定界符和双占位符 <!--# var a = [1,2,3]; --> <html></html> <script> //#for(var i in a){ var js${iLP.index} = "${i}"; //#}
FastDFS V6.0支持双IP特性介绍
    很高兴地告诉大家,经过半个多月的开发和测试,FastDFS v6.0发布,欢迎大家下载使用。      v6.0支持双IP,tracker server和storage server均支持双IP。v6.0新增特性说明如下:支持双IP,一个内网IP,一个外网IP,支持NAT方式的内网和外网双IP,解决跨机房或混合云部署问题。     双IP
Golang math基本数学函数
三角函数 ---- 正弦函数,反正弦函数,双曲正弦,反双曲正弦 * func Sin(x float64) float64 * func Asin(x float64) float64 * func Sinh(x float64) float64 * func Asinh(x float64) float64 一次性返回sin,cos
Linux云计算学习笔记day15
#引号系列 单引号        所见即所得                                               echo '$LANG {1..5}' 双引号  与单引号类似 双引号里面的特殊符号会被解析(运行)                                      
Python数据结构与算法——双端队列Dequeue
![](https://oscimg.oschina.net/oscnet/fa1ed5ef-abdf-40f3-9008-1750e73ed60e.png) 点击上方 蓝字 关注我们 **双端队列Dequeue** ------------------- 双端队列是一种有序的数据集,与队列相似,但双端队列的两端都可以作为队首
Sortable_readme双语翻译
Sortable   [![Financial Contributors on Open Collective](https://opencollective.com/Sortable/all/badge.svg?label=financial+contributors)](https://www.oschina.net/action/GoToLink?ur

热门文章

ConcurrentHashMap计算机网络数据库系统概论List集合操作系统

最新文章

数据库系统概论List集合ConcurrentHashMap计算机网络Java的其他Map