【字符串】【滑动窗口+位运算+双指针】1、无重复字符的最长子串+2、尽可能使字符串相等+3、最长优雅子数组+4、移动零+5、反转字符串

2道简单+3道中等

1、无重复字符的最长子串（难度：中等）

该题对应力扣网址

超时代码

老实说，在我写博客的时候，也不知道为啥超时了，因为我看和我AC的代码时间也差不了多少吧（如果有大佬知道，还请在评论区指点一下，抱拳）
写这个超时代码的过程中，也遇到了不少bug，确实体验了一把之前有大佬说，

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map <char,int> window;
        int left=0,right=0;
        int len = INT_MIN;
        if(s.length()==0){
            return 0;
        }
        while(right<s.length()){
            char c = s[right];
            right++;

            if(!window.count(c)){
                window[c]++;
            }
            //出现重复字符了
            else{
                if(right-1-left>len){
                    // cout<<right-1-left<<endl;
                    len=right-1-left;
                }
                while(window[c]==1){
                    char d = s[left];
                    left++;

                    window[d]--;
                }
                // left=right-1;
                right=right-1;
                // window.clear();
                // cout<<window<<endl;
            }
        }
        if(window[s[right-1]]==1 && right-left>len){
            // cout<<right-1-left<<endl;
            len=right-left;
        }
        return len;
    }
};

AC代码

套模板之后的代码（详情请看上一篇博客，这里就不多说了），非常顺利

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map <char,int> window;
        int left=0,right=0;
        int len = INT_MIN;
        if(s.length()==0){
            return 0;
        }
        while(right<s.length()){
            char c = s[right];
            right++;

            window[c]++;
            
            //出现重复字符了
        

            while(window[c]>1){
                char d = s[left];
                left++;

                window[d]--;
            }
            if(right-left>len){
                len=right-left;
            }

        }
        return len;
    }
};

2、尽可能使字符串相等（难度：中等）

该题对应力扣网址

AC代码

这个比之前做过的滑动窗口题还要简单

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        int left=0,right=0;
        int sum=0;
        int len=0;
        while(right<s.size()){
            char c=s[right];
            char c1=t[right];
            right++;
            sum+=abs(c-c1);
            //当开销大于预算，开始缩减窗口大小
            while(sum>maxCost){
                char d=s[left];
                char d1=t[left];
                left++;
                sum-=abs(d-d1);
            }
            if(right-left>len){
                len=right-left;
            }
        }
        return len;
    }
};

3、最长优雅子数组（难度：中等）

该题对应力扣网址

AC代码

依旧是滑动窗口的一套逻辑，在这道题里位运算运用的比较巧妙
第一次刷到位运算的题目
1、在扩大窗口的时候：当sum和新加入的数字相与为0，通过或运算sum|=a来存储新的数字的二进制里的1。（之所以存1是因为与，如果相与运算为0，那么运算双方的二进制表示里对应的数位，双方最多只有一个1。）
2、在缩小窗口的时候：使用异或操作sum^=b来“减去”这个数nums[left]（之所以异或操作能减去这个数，是因为sum是一个累计之后的结果，累计的这些结果肯定是在sum&a==0的条件下累计的，那么说明，在sum与a的二进制表示肯定没有相同的1位，因此异或就可以减去这个数，不明白的话可以再自己手写一下。）

class Solution {
public:
    int longestNiceSubarray(vector<int>& nums) {
        int left=0,right=0,sum=0,len=INT_MIN;
        while(right<nums.size()){
            int a=nums[right];
            right++;
            if((sum&a)==0){
                //存1
                sum|=a;
            }
            else{
                //缩小窗口
                while((sum&a)!=0){
                    int b=nums[left];
                    left++;
                    sum^=b;
                }
                sum|=a;

            }
            len=max(len,right-left);
        }
        return len;
    }
};

4、移动零（难度：简单）

该题对应力扣网址

AC代码

思路简单，双指针，先把不为0的挪到前面，剩下的填充0

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int l=0,r=0;
        while(r<nums.size()){
            if(nums[r]!=0){
                nums[l]=nums[r];
                l++;
            }
            r++;
        }
        for(int i=l;i<nums.size();i++){
            nums[i]=0;
        }
    }
};

5、反转字符串（难度：简单）

水题，双指针

该题对应力扣网址

AC代码

水题

class Solution {
public:
    void reverseString(vector<char>& s) {
        int l=0,r=s.size()-1;
        while(l<=r){
            swap(s[l],s[r]);
            l++;
            r--;
        }
    }
};