「算法刷题」双指针、滑动窗口的LeetCode题目实现

[TOC]

​

一、双指针的LeetCode题目

1、删除数组中的元素

（1）删除数组中的某个（所有的）目标值

27. 移除元素（简单难度）

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int n=nums.size();
        // 数组中至少有0个元素
        int slow=0; // 慢指针,[0,low),指向删除后的区间的最后一个元素的后一个索引
        int fast = 0;// 快指针，负责遍历整个数组
        while(fast < n)
        {
            //快指针不等于目标值时
            if (nums[fast] != val) 
            {
                nums[slow] = nums[fast];//快指针指向的数覆盖给慢指针指向的数
                slow++;//慢指针+1
                fast++; //快指针+1
            }
            // 快指针等于目标值时，快指针+1
            else{
                fast++;//快指针+1
            }
        }
        return slow;//返回慢指针
    }
};

（2）删除有序数组中的重复项

26. 删除有序数组中的重复项（简单难度）

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n=nums.size();
        if(n==0) return 0;
        // 数组中至少有1个元素
        int slow=1;// 慢指针,[0,low),指向删除后的区间的最后一个元素的后一个索引
        int fast=1;// 快指针，负责遍历整个数组
        while(fast<n){
            // 快指针和上一个元素不同时，
            if(nums[fast]!=nums[slow-1]){
                nums[slow]=nums[fast];// 快指针元素覆盖慢指针元素
                slow++;//慢指针前进
                fast++;//快指针前进
            }
            // 快指针和上一个元素相同时，快指针前进
            else{
                fast++;
            }
        }
        return slow;
    }
};

80. 删除有序数组中的重复项 II（中等难度）

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n=nums.size();
        if(n<=2) return n;
        // 数组中至少有2个元素
        int slow=2;// 慢指针,[0,low),指向删除后的区间的最后一个元素的后一个索引
        int fast=2;// 快指针，负责遍历整个数组
        while(fast<n){
            // 快指针不等于
            if(nums[fast]!=nums[slow-2]){
                nums[slow]=nums[fast];
                slow++;
                fast++;
            }
            else{
                fast++;
            }
        }
        return slow;
    }
};

2、移动数组中的元素

283. 移动零（简单难度）

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n=nums.size();
        // 数组中至少有0个元素
        int slow=0;// 慢指针,[0,low),指向移动后的区间的最后一个元素的后一个索引
        int fast=0;// 快指针，负责遍历整个数组
        while(fast<n){
            // 如果快指针不为0
            if(nums[fast]!=0){
                swap(nums[slow],nums[fast]);// 快慢交换
                slow++;
                fast++;
            }
            else{
                fast++;
            }
        }
    }
};

75. 颜色分类（中等难度）

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n=nums.size();
        if(n<2) return;
        // 整个数组需要分成3个区间:
        int zero = 0;//[0,zero)，红色元素,存放0
        int one = 0;//[zero,one)，白色元素，存放1,同时负责遍历
        int two = n-1;// [one,two)，篮色元素，存放2
        while (one < n) {
            // 如果当前元素==0,移动到头部
            if (nums[one] == 0&&zero<one) {
                swap(nums[one], nums[zero]);//
                zero++;
            }
            // 如果当前元素==2,移动到表尾
            else if (nums[one] == 2&& one<two) {
                swap(nums[one], nums[two]);
                two--;
            }
            // 如果当前元素==1，跳过
            else {
                one++;
            }
        }
        //quickSort(nums,0,nums.size()-1);
    }
}

215. 数组中的第K个最大元素（中等难度）

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int len = nums.size();
        return quickFind(nums,k-1,0,len-1);//从大到小排序，第k大就是第k-1个索引，返回第k-1个索引的值
    }
    // 快排法
    int quickFind(vector<int>& nums, int k,int left,int right){
        int index = partition(nums,left,right);//开始分区
        // 结束分区
        if(index==k){
            return nums[index];//first是基准值索引，表示第first个
        }
        else if(index>k){
            return quickFind(nums, k,left,index-1);
        }
        else {
            return quickFind(nums, k,index+1,right);
        }
    }
    // 分区函数
    int partition (vector<int> &nums, int first, int last) {
        int key = nums[first];//默认第一个为基准值
        while (first < last) {
            // 从右往左找到第一个小于key的值
            while (first < last && nums[last] <= key) --last;
            nums[first] = nums[last];
            // 从左往右找到第一个大于key的值
            while (first < last && nums[first] >= key) ++first;
            nums[last] = nums[first];
        }
        nums[first] = key;// 基准值归位
        return first;// 返回索引
    } 
};

905. 按奇偶排序数组（简单难度）

class Solution {
public:
    /*思路：这道题解决不难，使用额外的数组，只要会判断奇偶数就可以分出两类数，难点在于原地排序算法：双指针的方法：
    左指针寻找奇数值，右指针寻找偶数值，当符合交换条件时，进行两数交换；
    否则指针继续左右运动，寻找符合条件的奇偶值。
    当两指针相遇时，结束循环。*/
    vector<int> sortArrayByParity(vector<int>& nums) {
        int left=0;//左指针
        int right=nums.size()-1;//右指针
        // 遍历数组[left,right],
        while(left<right){
            // 如果左指针指向奇数，右指针指向偶数，就交换两个数
            if (nums[left] % 2 > nums[right] % 2) {
                swap(nums[left],nums[right]);
            }
            // 如果左指针指向偶数，左指针移动
            if (nums[left] % 2 == 0) left++;
            // 如果右指针指向奇数，右指针移动
            if (nums[right] % 2 == 1) right--;
        }
        return nums;
    }
};

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面（简单难度）

class Solution {
public:
    /*思路：这道题解决不难，使用额外的数组，只要会判断奇偶数就可以分出两类数，难点在于原地排序算法：双指针的方法：
    左指针寻找偶数值，右指针寻找奇数值，当符合交换条件时，进行两数交换；
    否则指针继续左右运动，寻找符合条件的奇偶值。
    当两指针相遇时，结束循环。*/
    vector<int> exchange(vector<int>& nums) {
        int left=0;//左指针
        int right=nums.size()-1;//右指针
        // 遍历数组[left,right],
        while(left<right){
            // 如果左指针指向偶数，右指针指向奇数，就交换两个数
            if (nums[left] % 2 < nums[right] % 2) {
                swap(nums[left],nums[right]);
            }
            // 如果左指针指向奇数，左指针移动
            if (nums[left] % 2 == 1) left++;
            // 如果右指针指向偶数，右指针移动
            if (nums[right] % 2 == 0) right--;
        }
        return nums;
    }
};

922. 按奇偶排序数组 II（简单难度）

class Solution {
public:
    /*思路：这道题解决不难，使用额外的数组，只要会判断奇偶数就可以分出两类数，难点在于原地排序算法：双指针的方法：
    遍历所有偶数索引*/
    vector<int> sortArrayByParityII(vector<int>& nums) {
        //
        int n = nums.size();
        int j = 1;//奇数索引
        // 遍历整个数组的所有偶数索引
        for (int i = 0; i < n; i += 2) {
            // 如果偶数索引上的数是奇数
            if (nums[i] % 2 == 1) {
                // 连续遍历整个数组的所有奇数索引，找到一个数是偶数
                while (nums[j] % 2 == 1) j += 2;
                swap(nums[i], nums[j]);//交换两个数
            }
        }   
        return nums;
    }
};

3、查找排序数组中的2个数

剑指 Offer 57. 和为s的两个数字（简单难度）

剑指 Offer II 006. 排序数组中两个数字之和（简单难度）

class Solution {
public:
    /*解析：这道题在一个排序数组中查找2个数，使其和为target
    提到排序，可能会选用二分查找法，二分查找法确实可以结合使用
    但是这道题难度简单，用普通的双指针就可以搞定
    排序数组的特点可以作为移动左右指针的依据，和较小右移左指针，和较小左移右指针
    */
    vector<int> twoSum(vector<int>& nums, int target) {
        int left=0;//左指针
        int right=nums.size()-1;//右指针
        int sum=0;
        while(left<=right){
            sum=nums[left]+nums[right];
            // 如果两数和==target，直接返回
            if(sum==target) return {nums[left],nums[right]};
            // 如果两数和>target，说明应该降低两数和，右指针左移即可
            else if(sum>target) right--;
            // 如果两数和<target，说明应该增加两数和，左指针右移即可
            else left++;
        }
        return {nums[left],nums[right]};
    }
};

二、滑动窗口的LeetCode题目

1、连续递增子数组

674. 最长连续递增序列（简单难度）

子数组是原数组中连续的元素，中间不可以删除或添加其他元素，每个元素的相对顺序和原数组相同

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int len=nums.size();
        if(len==1) return 1;
        int res=0;// 最长长度
        int left=0;
        int right=1;
        // 滑动窗口[left,right)表示递增区间，负责搜索数组中的所有递增区间
        while(right<len){
            // 如果新元素递增，扩展右边界
            if(nums[right-1]<nums[right]){
                right++;
            }
            // 如果新元素非递增，更新左边界，扩展右边界
            else{
                left=right;
                right++;
            }
            res=max(res,right-left);//不断更新递增区间的最大长度
        }
        return res;
    }
};

剑指 Offer 57 - II. 和为s的连续正数序列（简单难度）

class Solution {
public:
    /*解析：本题是从正整数序列中查找所有和为target的连续子序列
    难点在于每个连续子序列的长度、数量是不确定的。
    这种类型题，特别是元素都是正整数，特别适合滑动窗口算法。
    请注意，左指针和右指针的移动时机
    当区间和>=target,右移左指针；当区间和<target，右移右指针
    进阶：求解区间和的数学技巧：(left+right)*(right-left+1)/2
    */
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>> res;
        int left=1;//正整数序列的第1个数
        int right=2;//正整数序列的第2个数
        int sum=0;
        vector<int> sub;
        // 滑动窗口[left,right]
        while(left<right){
            // 计算滑动窗口[left,right]的和
            sum=0;
            sub.clear();
            for(int i=left;i<=right;i++){
                sum+=i;
                sub.push_back(i);
            }
            // 如果区间和==target，移动左指针
            if(sum==target) {
                res.push_back(sub);
                left++;
            }
            // 如果区间和<target,右指针右移
            else if(sum<target) right++;
            // 如果区间和>target,左指针右移
            else left++;
        }
        return res;
    }
};

添加数学公式优化后：

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>> res;
        int left=1;//正整数序列的第1个数
        int right=2;//正整数序列的第2个数
        int sum=0;
        vector<int> sub;
        // 滑动窗口[left,right]
        while(left<right){
            // 计算滑动窗口[left,right]的和
            sum=(left+right)*(right-left+1)/2;
            // 如果区间和==target，移动左指针
            if(sum==target) {
                sub.clear();
                for(int i=left;i<=right;i++){
                    sub.push_back(i);
                }
                res.push_back(sub);
                left++;
            }
            // 如果区间和<target,右指针右移
            else if(sum<target) right++;
            // 如果区间和>target,左指针右移
            else left++;
        }
        return res;
    }
};