leetcode：滑动窗口

class Solution {
public:
    long long maxSum(vector<int>& nums, int m, int k) {
        long long ans = 0, sum = 0;
        unordered_map<int, int>
            cnt; //如何把重复的数字算成一个数字，就要用到数组来进行计数了，重复的数字对应的值大于1
        for (int i = 0; i < k - 1; i++) //先求前k-1个数
        {
            sum += nums[i];
            cnt[nums[i]]++;
        }
        for (int i = k - 1; i < nums.size(); i++) //进去一个出来一个，满足k个数
        {
            sum += nums[i];
            cnt[nums[i]]++;
            if (cnt.size() >= m) //判断是否有m个不相同的数
                ans = max(ans, sum);

            int out = nums[i - k + 1];
            sum -= out;
            if (--cnt[out] == 0) //如果只出现1次，可以直接删除
                cnt.erase(out);
        }
        return ans;
    }
};

class Solution {
public:
    long long maximumSubarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        long long res = 0, sum = 0;
        for (int i = 0; i < k - 1; i++) {
            sum += nums[i];
            mp[nums[i]]++;
        }
        for (int i = k - 1; i < nums.size(); i++) {
            sum += nums[i];
            mp[nums[i]]++;
            if (mp.size() == k ) res =max(res,sum);//这个已经去重了，只要当mp的大小等于k时，才会更新res的大小，否则说明有重复数字，不更新
            int x = nums[i - k + 1];
            if (--mp[x] == 0) mp.erase(x);//及时清除为0的数字
            sum -= x;
        }
        return res;
    }
};

class Solution {
public:
    int maxSubarrayLength(vector<int>& nums, int k) {
        unordered_map<int,int>cnt;
        int ans=0,l=0;
        for(int r=0;r<nums.size();r++)
        {
            cnt[nums[r]]++;
            while(cnt[nums[r]]>k)//如果有元素的出现频率大于k,就要不断左移左指针,直到这个元素的出现频率小于等于k,如果这个元素
                cnt[nums[l++]]--;
            ans=max(ans,r-l+1);
        }
        return ans;
    }
};

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        multiset<int>st;//关键在于找每个区间的最大值和最小值，如果遍历寻找，就会超时，所以要找到一个合适的数据结结构
        //我们知道set/multiset/map是有序的，set会去重，所以我们使用multiset
        int l=0;
        int res=0;
        for(int r=0;r<nums.size();r++)
        {
            st.insert(nums[r]);
            while(*st.rbegin()-*st.begin()>limit)
            {
                st.erase(st.find(nums[l]));
                l++;
            }
            res=max(res,r-l+1);
        }
        return res;
    }
};

class Solution {
public:
    int minOperations(vector<int> &nums, int x) {   //正难则反 逆向思维
        int target = accumulate(nums.begin(), nums.end(), 0) - x;
        if (target < 0) return -1;
        int ans = -1, l = 0, sum = 0, n = nums.size();
        for (int r = 0; r < n; r++) {
            sum += nums[r];
            while (sum > target) sum -= nums[l++]; 
            if (sum == target) ans = max(ans, r - l + 1);
        }
        return ans < 0 ? -1 : n - ans;
    }
};