算法2：滑动窗口(上）

文章目录

长度最小子数组
无重复字符的最长子串
[最大连续 1 的个数III](https://leetcode.cn/problems/max-consecutive-ones-iii/description/)
将x减到0的最小操作数

长度最小子数组

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

无重复字符的最长子串

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        int left = 0, right = 0;
        int hash[127] = {0};
        int res = 0;

        while (right < n) {
            hash[s[right]]++; // 进窗口，右端滑动
            if (hash[s[right]] > 1) {
                while (hash[s[left]] != hash[s[right]])
                    hash[s[left++]]--;
                hash[s[left++]]--;
            } else {
                res = max(res, right - left + 1);
            }
            right++;
        }
        return res;
    }
};


int max(int a, int b)
{
    return a > b ? a : b;
}
int lengthOfLongestSubstring(char * s){
    int n = strlen(s);
    int left = 0, right = 0, res = 0;
    int hash[127] = {0};
    while(right < n)
    {
        hash[s[right]]++;
        while(hash[s[right]] > 1)
            hash[s[left++]]--;
        res = max(res,right - left + 1);
        right++;
    }
    return res;
}

解析：

最大连续 1 的个数III

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int res = 0,zero = 0;
        for(int left = 0,right = 0; right < nums.size();right++)
        {
            if(nums[right] == 0)    zero++;//进窗口
            while(zero > k)
            {
                if(nums[left++] == 0) zero--;
            }    
            res = max(res,right - left + 1);
        }
        return res;
    }
};

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int left = 0, right = 0;
        int zero = 0, res = 0;
        while (right < nums.size()) {
            // 进窗口
            while (right < nums.size() && nums[right])
                right++;
            // 判断
            if (right < nums.size() && ++zero <= k) {
                right++;
                // 数据更新
                res = max(res, right - left);
            } else {
                // 数据更新
                res = max(res, right - left);
                // 出窗口
                while (left < right && nums[left])
                    left++;
                k--;
                left++;
                right++;
            }
        }
        return res;
    }
};

将x减到0的最小操作数

正难则反

该题从正面去解，一会儿左一会儿右全凭场景所变化，编码写起来非常繁琐；此时，运用数学思维反证法来解决会不会简单些呢？该题需要求最小操作数，那也就意味着剩下的数据量是最大的，而且因为每次操作都在最左或者最右边，那也就是说剩下的数据是原数据的连续子串;OK，现在我们只需要求出一个符合的尽可能保证数据量大且其sum值等于sum(nums) - x 的连续子串即可.

那现在将符合要求数据看成一个窗口往后滑动即可。

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int sum = 0;
        for(int e : nums)   sum += e;
        if(x > sum) return -1;
        if(x == sum) return nums.size();
        int target = sum - x;
        int res = -1;
        for(int left = 0, right = 0, tmp = 0; right < nums.size(); right++)
        {
            tmp += nums[right];//进窗口
            while(tmp >= target)
            {
                if(tmp == target)   res = max(res, right - left +1);//判断+记录长度
                tmp -= nums[left++];// 出窗口
            }
        }

        if(res == -1)
            return res;
        return nums.size() - res;
    }
};

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int sum = 0;
        for (int e : nums)
            sum += e;
        if (x > sum)
            return -1;//细节
        int target = sum - x;
        int res = -1;
        for (int left = 0, right = 0, tmp = 0; right < nums.size(); right++) {
            tmp += nums[right]; // 进窗口
            while (tmp > target) // 判断
                tmp -= nums[left++]; // 出窗口
            if (tmp == target)
                res = max(res, right - left + 1); // 更新数据
        }

        if (res == -1)
            return res;
        return nums.size() - res;
    }
};