双指针问题

BichonCode 等级 969 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,右
爬取五大平台621款手机,告诉你双十一在哪买最便宜!
↑关注+置顶 有趣的不像个技术号 今晚0点,相约剁手大家好,我是朱小五 明天就是双十一了,看了看自己手里的卡的像IE浏览器的手机,感觉可能等不到5G普及了。 我!要!换!手!机! 去哪买呢? 作为一个机(pin)智(qiong)boy,肯定要比价啊,哪家便宜去哪家 我用Python爬取了某比价网站的手机数据,获取了其中五大平台(天猫,京东,
Java面试常被问到这道题:如何保证缓存与数据库的双写一致性?
**面试原题:如何保证缓存与数据库的双写一致性?** ![](https://oscimg.oschina.net/oscnet/up-e90c4aee3693a52b8243508bc7a22c0af71.JPEG) ### **面试官心理分析** ![](https://oscimg.oschina.net/oscnet/up-5790cf915b
12.25聚惠双旦,超低折扣
**聚惠双旦,超低折扣** 双!旦!活!动!来!袭! 如果你为错过双十一和双十二而遗憾,那千万别再错过双旦了,2020年年末,51CTO学院为新老用户送上一份“**双旦大礼**”! **视频课程全场6折!** **学习路径8折!** **会员6折!** **活动时间:12月25日-12月31日** 长按识别海报,提前将课程加购,
virtualbox 双网卡设置
此文章不是本人研究出来的结果,仅仅是转发。。本人配置网络时,发现了很多文章,大多是天下文章一大抄,基本上效果不佳,要么就是语焉不详。这个文章文字精简,内容简单,易于理解,最重要的是好用。。原文地址: [http://www.linuxidc.com/Linux/2015-02/112986.htm](https://www.oschina.net/acti
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
MSTP+VRRP+OSPF+双出口
拓扑图 === ![MSTP+VRRP+OSPF+双出口](https://s4.51cto.com/images/blog/202012/14/3e101c381bc712f9915994275649ac00.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFF
Openstack(三)Haproxy+Keepalived双机
### 3.1部署keepalived #### 3.1.1下载keepalived源码包,并解压 \# wget [http://www.keepalived.org/software/keepalived-1.4.2.tar.gz](https://www.oschina.net/action/GoToLink?url=http%3A%2F%2Fww
Prometheus相关项目Thanos与Cortex 双双进入CNCF孵化器
![](https://oscimg.oschina.net/oscnet/ea87a69a-082d-4e9b-b878-d4be478becb9.jpg) ![](https://oscimg.oschina.net/oscnet/666cde8b-65b7-42d3-a30c-89a0a19cb78d.jpg) **导语** Thanos
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

热门文章

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

最新文章

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