双指针问题

BichonCode 37 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--];
    }
};
预览图
收藏
评论区
守株待兔
最新文章
数据库系统概论 2021-01-23 11:49
List集合 2021-01-23 11:47
ConcurrentHashMap 2021-01-23 11:46
计算机网络 2021-01-23 11:45
Java的其他Map 2021-01-23 11:43
软件工程 2021-01-23 11:38
大数据排序 2021-01-23 11:37
操作系统 2021-01-23 11:29

导读