algo-aha

滑动窗口写法"hi移一步、lo移多步"，可以解"至多K"问题atMost(K)

• ”刚好K“问题exactly(K)=atMost(K)-atMost(K-1)

联想：atLeast(K)问题只能解全正数数组的最短子段，需要 1.全正数 2.atLeastK 3.求最短。见子段和>=T

无重复字符的最长子段

窗口内至多一个

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

int lengthOfLongestSubstring(string s) {
    const int N = s.size();
    unordered_map<char, int> cnt;
    int ans = 0;
    for (int hi = 0, lo = 0; hi < N; hi++) {
        cnt[s[hi]]++;
        while (cnt[s[hi]] > 1) {
            cnt[s[lo]]--;
            lo++;
        }
        ans = max(ans, hi - lo + 1);
    }
    return ans;
}

至多K个不同字符的最长子段

• https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/

int lengthOfLongestSubstringKDistinct(string s, int k) {
    unordered_map<int, int> cnt; // char=>count
    int ans = 0;
    for (int hi = 0, lo = 0; hi < s.size(); hi++) {
        if (cnt[s[hi]]++ == 0) k--;
        while (k < 0) {
            if (--cnt[s[lo]] == 0) k++;
            lo++;
        }
        ans = max(ans, hi - lo + 1);
    }
    return ans;
}

把01数组的<=K位0改成1，连续1的最长子段长

• https://leetcode.com/problems/max-consecutive-ones-iii/
• https://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element/

int longestOnes(vector<int>& A, int K) {
    const int N = A.size();
    int zeroCnt = 0, ans = INT_MIN;
    for (int hi = 0, lo = 0; hi < N; hi++) {
        if (A[hi] == 0) zeroCnt++;
        while (zeroCnt > K) {
            if (A[lo++] == 0) zeroCnt--;
        }
        ans = max(ans, hi - lo + 1);
    }
    return ans;
}

含K个不同数的子段个数

• https://leetcode.com/problems/subarrays-with-k-different-integers/
• https://leetcode.com/problems/binary-subarrays-with-sum/
• https://leetcode.com/problems/count-number-of-nice-subarrays

int subarraysWithKDistinct(vector<int>& A, int K) {
    return atMost(A, K) - atMost(A, K-1);
}

int atMost(vector<int>& A, int K) {
    const int N = A.size();
    unordered_map<int, int> cnt; // num=>count
    int ans = 0;
    for (int hi = 0, lo = 0; hi < N; hi++) {
        if (cnt[A[hi]]++ == 0) K--;
        while (K < 0) {
            if (--cnt[A[lo]] == 0) K++;
            lo++;
        }
        ans += hi - lo + 1;
    }
    return ans;
}

长为K的最小和子段

• https://leetcode.com/problems/maximum-points-you-can-obtain-from-cards/

简单的情况，可不用atMost(K)-atMost(K-1)写法

int maxScore(vector<int>& cardPoints, int k) {
    // 变为：找长=N-k的最小和子段
    const int N = cardPoints.size();
    int totalSum = 0, subSum = 0, minSum = INT_MAX;
    for (int hi = 0, lo = 0; hi < N; hi++) {
        totalSum += cardPoints[hi];
        subSum += cardPoints[hi];
        if (hi - lo + 1 > N - k) {
            subSum -= cardPoints[lo];
            lo++;
        } 
        if (hi - lo + 1 == N - k) {
            minSum = min(minSum, subSum);
        }
    }
    return totalSum - minSum;
}