滑动窗口_⻓度最⼩的⼦数组⽆重复字符的最⻓⼦串将x减到0的最⼩操作数

⻓度最⼩的⼦数组（medium

https://leetcode.cn/problems/minimum-size-subarray-sum/

思路一：两个指针，p1 p2同时指向第一个元素。sum+=p2,如果sum<target，p2++直到大于，然后记录len=right-left。p1 p2再同时指向第二个元素，再不断循环。直到p2越界。

思路2：滑动窗口

其实在思路一基础上，p2没必要再退回到p1的位置，p1++后在原sum基础上减去p1原本指向的值，再判断sum和target大小。

这种两个指针向同一个方向移动，p1p2的范围就像窗口一样，在数组上移动，它可以是动态的，也可以是固定的。

1.left right窗口范围

2.进窗口

3.判断

4.出窗口

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left=0,right=0,sum=0,len=INT_MAX;
        int n=nums.size();
        for(;right<n;right++)
        {
            sum+=nums[right];//进窗口
            while(sum>=target)//判断
            {
                len=min(len,right-left+1);//更新结果
                sum-=nums[left];//出窗口
                left++;
            }
        }
        return len==INT_MAX?0:len;
    }
};

⽆重复字符的最⻓⼦串（medium）

https://leetcode.cn/problems/longest-substring-without-repeating-characters/

思路：从第一个字符开始，到最后一个字符，一个一个算不重复的最长子字符串。

确实可以算但可以进行优化，

eg. de abc abcdefj 从第一个字符算最长子字符串deabc，从第二个算eabc 第三个abc

可以看到不重复子字符串的长度是不断变小的，因为只要子字符串中还包含a也就是重复的字符，就不可能增加。

所以用滑动窗口时，从左到右不断进窗口，等到出现重复字符时，先更新，再不断出窗口，直到把重复字符删除。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> charSet;
        int len=0;
        int left=0;
        for(int right=0;right<(int)s.size();right++)
        {
            while(charSet.find(s[right])!=charSet.end())//判断
            {
               charSet.erase(s[left]);//出窗口
               left++;
            }
            len=max(len,right-left+1);//更新结果
            charSet.insert(s[right]);//入窗口
        }
        return len;
    }
};

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int hash[128];
        int re=0;
        int left=0,right=0;
        while(right<s.size())
        {
            hash[s[right]]++;   //入窗口
            if(hash[s[right]]>1)//已经存在 出窗口直到只存在一种该字母
            {
                while(hash[s[right]]!=1)
                {
                    hash[s[left++]]--;
                }
            }
            //记录结果
            re=max(re,right-left+1);
            //遍历下一个
            right++;
        }
        return re;
    }
};

将x减到0的最⼩操作数(medium)

. - 力扣（LeetCode）

如果从正面想会有困难，可以用逆向思维想一想。

从左右两边找最少的数==x,也就是从中间找最多的数==数组和-x

就转成找最长字符串问题，可以用滑动窗口解决。

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int sum=0,ret=-1;
        int left=0,right=0;
        for(auto &o:nums) sum+=o;
        sum-=x;
        //数组和小于x
        if(sum<0) return -1;
        //if(sum==0) return (int)nums.size();
        for(int k=0;right<(int)nums.size();right++)
        {
            k+=nums[right];
            while(k>sum)
            {
                k-=nums[left++];
            }
            if(k==sum)  ret=max(ret,right-left+1);
        }
        return ret==-1?-1:(int)nums.size()-ret;
    }
};

ret=0;

return ret==0?-1:(int)nums.size()-ret;

改成这样可以吗？

为什么出错？
当数组和==x时，此时每次循环结束前left都++，right循环结束后才能++，那么当right指向最后一个元素，left就已经指向最后一个元素后面。当算ret=max(ret,right-left+1) 相当于max(0,0)。结果ret==0,这种情况和没有找到的情况重合，所以ret设为-1可以区别开来。

或者直接加上if(sum==0) return (int)nums.size(); 先把数组和相等的情况排除。