滑动窗口

模板

from collections import defaultdict
def windows(s, k):
    hashmap = defaultdict(int)
    left = 0 
    res = 0
    for i, c in enumerate(s):
        hashmap[c] += 1 # 将当前的字符串放入窗口中
        while len(hashmap) > k:
           temp = s[left]
           hashmap[temp] -= 1
           if hashmap[temp] == 0:
               del hashmap[temp]
           left += 1
        res = max(res, i - left + 1)
    return res

30. 串联所有单词的子串

给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s中恰好可以由 words中所有单词串联形成的子串的起始位置。
注意子串要与 words中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。

示例 1：
输入：s = “barfoothefoobarman”, words = [“foo”,”bar”] 输出：[0,9] 解释： 从索引 0 和 9 开始的子串分别是 “barfoo” 和 “foobar” 。 输出的顺序不重要, [9,0] 也是有效答案。
示例 2：
输入：s = “wordgoodgoodgoodbestword”, words = [“word”,”good”,”best”,”word”] 输出：[]
示例 3：
输入：s = “barfoofoobarthefoobarman”, words = [“bar”,”foo”,”the”] 输出：[6,9,12]

提示：

• 1 <= s.length <= 104
• s 由小写英文字母组成
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 30
• words[i] 由小写英文字母组成

import collections

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        word_nums = collections.Counter(words)
        len_ = len(words[0])
        total_len = len_ * len(words)
        left = 0
        res = []
        for i in range(len(s) - total_len + 1):
            temp_nums = collections.defaultdict(int)
            index = i 
            while index < i + total_len:
                temp = s[index: index + len_]
                if temp not in word_nums or temp_nums[temp] == word_nums[temp]:
                    break 
                temp_nums[temp] += 1
                index += len_
            if index == i + total_len:
                res.append(i)
        return res

关键点：

if temp not in word_nums or temp_nums[temp] == word_nums[temp]:
    break

如果当前字符串不在words中， 同时数量上已经等于 temp_nums, 则之后再放入temp_nums肯定会超过原words的数量，因此直接break

import collections

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        words_map = collections.Counter(words)
        m = len(s)
        n = len(words[0])
        res = []
        for i in range(m - n + 1):
            temp = collections.defaultdict(int)
            for j in range(i, m - n + 1, n):
                ch = s[j: j + n]
                if ch not in words_map or words_map[ch] == temp[ch]:
                    break 
                temp[ch] += 1
            if words_map == temp:
                res.append(i)
        return res

76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？

示例 1：
输入：s = “ADOBECODEBANC”, t = “ABC” 输出：“BANC”
示例 2：
输入：s = “a”, t = “a” 输出：“a”
示例 3:
输入: s = “a”, t = “aa” 输出: “” 解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中， 因此没有符合条件的子字符串，返回空字符串。

提示：

• 1 <= s.length, t.length <= 105
• s 和 t 由英文字母组成

import collections

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if len(s) < len(t):
            return ""
        windows = collections.Counter(t)
        left = 0
        res = ""
        min_len = float('inf')
        for right, c in enumerate(s):
            windows[c] -= 1
            valied = False
            while self.is_valied(windows):
                windows[s[left]] += 1
                left += 1
                valied = True
            if valied and (right - left + 1) < min_len:
                res = s[left - 1: right + 1]
                min_len = right -left + 1
        return res

    def is_valied(self, windows):
        for k, v in windows.items():
            if v > 0:
                return False
        return True

978. 最长湍流子数组

当 A 的子数组 A[i], A[i+1], …, A[j] 满足下列条件时，我们称其为湍流子数组：

• 若 i <= k < j，当 k 为奇数时， A[k] > A[k+1]，且当 k 为偶数时，A[k] < A[k+1]；
• 或 若 i <= k < j，当 k 为偶数时，A[k] > A[k+1] ，且当 k 为奇数时， A[k] < A[k+1]。

也就是说，如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是湍流子数组。
返回 A 的最大湍流子数组的长度。

示例 1：
输入：[9,4,2,10,7,8,8,1,9] 输出：5 解释：(A[1] > A[2] < A[3] > A[4] < A[5])
示例 2：
输入：[4,8,12,16] 输出：2
示例 3：
输入：[100] 输出：1

提示：

1. 1 <= A.length <= 40000
2. 0 <= A[i] <= 10^9

通过次数42,940
提交次数90,710

错误的解答
湍流 说明有2种情况

1. 小大小大小大….
2. 大小大小大小…..

所以自己写的答案里总是只能过一半的用例

def maxTurbulenceSize(arr):
    left = 0
    right = 0
    res = 0
    while right < len(arr) - 1:
        right += 1
        if right % 2 == 0:  # 偶数
            if arr[right] <= arr[right - 1]:
                left = right
        else:
            if arr[right] >= arr[right - 1]:
                left = right
        res = max(res, right - left + 1)

    print(res)

官方解答

class Solution {
    public int maxTurbulenceSize(int[] arr) {
        int n = arr.length;
        int ret = 1;
        int left = 0, right = 0;

        while (right < n - 1) {
            if (left == right) {
                if (arr[left] == arr[left + 1]) {
                    left++;
                }
                right++;
            } else {
                if (arr[right - 1] < arr[right] && arr[right] > arr[right + 1]) {
                    right++;
                } else if (arr[right - 1] > arr[right] && arr[right] < arr[right + 1]) {
                    right++;
                } else {
                    left = right;
                }
            }
            ret = Math.max(ret, right - left + 1);
        }
        return ret;
    }
}


作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/longest-turbulent-subarray/solution/zui-chang-tuan-liu-zi-shu-zu-by-leetcode-t4d8/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

反方向思考，使用排除法
记arr[i] > arr[i + 1]为大
记arr[i] < arr[i + 1]为小
记arr[i] == arr[i + 1]为等

那么连续的
大 小 大 小 大……
或
小 大 小 大 小……
就是湍流子数组

那么什么时候不满足呢？

很明显，当出现：
1.连续的大 大
2.连续的小 小
3.等

换成代码就是：
1.arr[i - 1] > arr[i] && arr[i] > arr[i + 1]
2.arr[i - 1] < arr[i] && arr[i] < arr[i + 1]
3.arr[i] == arr[i + 1]

那么我们只需排除这三种情况即可！

话不多说，直接看代码！
代码

class Solution {
   public int maxTurbulenceSize(int[] arr) {
        int length = arr.length;
        // 最大湍流子数组的长度
        int maxLength = 1;
        // 当前湍流子数组的长度
        int nowLength = 1;
        for (int i = 0; i < length - 1; i++) {
            if (arr[i] < arr[i + 1]) {
                nowLength++;
                // 连续出现 小 小
                if (i != 0 && arr[i - 1] < arr[i]) {
                    nowLength = 2;
                // 更新最大湍流子数组的长度
                } else if (nowLength > maxLength) {
                    maxLength = nowLength;
                }
            } else if (arr[i] > arr[i + 1]) {
                nowLength++;
                // 连续出现 大 大
                if (i != 0 && arr[i - 1] > arr[i]) {
                    nowLength = 2;
                // 更新最大湍流子数组的长度
                } else if (nowLength > maxLength) {
                    maxLength = nowLength;
                }
            // 出现 等 arr[i] == arr[i + 1]
            } else {
                nowLength = 1;
            }
        }
        return maxLength;
    }
}

作者：uive
链接：https://leetcode-cn.com/problems/longest-turbulent-subarray/solution/pai-chu-fa-miao-dong-by-uive-sfei/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

3. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:
输入: s = “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: s = “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: s = “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。
示例 4:
输入: s = “” 输出: 0

提示：

• 0 <= s.length <= 5 * 104
• s 由英文字母、数字、符号和空格组成

from collections import defaultdict

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        hashmap = defaultdict(int)
        left = 0
        res = 0
        for i, c in enumerate(s):
            hashmap[c] += 1
            while hashmap[c] > 1:
                hashmap[s[left]] -= 1
                left += 1
            res = max(res, i - left + 1)
        return res

import collections

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        hashmap = collections.defaultdict(int)
        left = 0
        res = 0
        for right in range(len(s)):
            ch = s[right]
            hashmap[ch] += 1
            while hashmap[ch] > 1:
                hashmap[s[left]] -= 1
                left += 1
            res = max(res, right - left + 1)
        return res

159. 至多包含两个不同字符的最长子串

给定一个字符串 s ，找出 至多 包含两个不同字符的最长子串 t，并返回该子串的长度。
示例 1:
输入: “eceba” 输出: 3 解释: t 是 “ece”，长度为3。
示例 2:
输入: “ccaabbb” 输出: 5 解释: t 是 “aabbb”，长度为5。
通过次数16,452
提交次数30,005

from collections import defaultdict
class Solution:
    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
        hashmap = defaultdict(int)
        left = 0
        res = 0
        for i, c in enumerate(s):
            hashmap[c] += 1
            while len(hashmap) > 2: # 如果超出了2个
                temp = s[left] # 窗口左边的值
                hashmap[temp] -= 1
                if hashmap[temp] == 0:
                    del hashmap[temp]
                left += 1
            res = max(res, i - left + 1)
        return res

340. 至多包含 K 个不同字符的最长子串

给定一个字符串s ，找出 至多 包含k 个不同字符的最长子串 T。

示例 1:
输入: s = “eceba”, k = 2 输出: 3 解释: 则 T 为 “ece”，所以长度为 3。
示例 2:
输入: s = “aa”, k = 1 输出: 2 解释: 则 T 为 “aa”，所以长度为 2。

提示：

• 1 <= s.length <= 5 * 104
• 0 <= k <= 50

通过次数12,272
提交次数24,862

from collections import defaultdict

class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        hashmap = defaultdict(int)
        left = 0
        res = 0
        for i, c in enumerate(s):
            hashmap[c] += 1
            while len(hashmap) > k:
                temp = s[left]
                hashmap[temp] -= 1
                if hashmap[temp] == 0:
                    del hashmap[temp]
                left += 1
            res = max(res, i - left + 1)
        return res

2024. 考试的最大困扰度

一位老师正在出一场由 n 道判断题构成的考试，每道题的答案为 true （用 ‘T’ 表示）或者 false （用 ‘F’ 表示）。老师想增加学生对自己做出答案的不确定性，方法是 最大化 有 连续相同 结果的题数。（也就是连续出现 true 或者连续出现 false）。
给你一个字符串 answerKey ，其中 answerKey[i] 是第 i 个问题的正确结果。除此以外，还给你一个整数 k ，表示你能进行以下操作的最多次数：

• 每次操作中，将问题的正确答案改为 ‘T’ 或者 ‘F’ （也就是将 answerKey[i] 改为 ‘T’ 或者 ‘F’ ）。

请你返回在不超过 k 次操作的情况下，最大 连续 ‘T’ 或者 ‘F’ 的数目。

示例 1：
输入：answerKey = “TTFF”, k = 2 输出：4 解释：我们可以将两个 ‘F’ 都变为 ‘T’ ，得到 answerKey = “TTTT“ 。 总共有四个连续的 ‘T’ 。
示例 2：
输入：answerKey = “TFFT”, k = 1 输出：3 解释：我们可以将最前面的 ‘T’ 换成 ‘F’ ，得到 answerKey = “FFF_T” 。 或者，我们可以将第二个 ‘T’ 换成 ‘F’ ，得到 answerKey = “TFFF“ 。 两种情况下，都有三个连续的 ‘F’ 。
示例 3：
输入：answerKey = “TTFTTFTT”, k = 1 输出：5 解释：我们可以将第一个 ‘F’ 换成 ‘T’ ，得到 answerKey = “TTTTTFTT” 。 或者我们可以将第二个 ‘F’ 换成 ‘T’ ，得到 answerKey = “TTFTTTTT_” 。 两种情况下，都有五个连续的 ‘T’ 。

提示：

• n == answerKey.length
• 1 <= n <= 5 * 104
• answerKey[i] 要么是 ‘T’ ，要么是 ‘F’
• 1 <= k <= n

import collections

class Solution:
    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:
        return max(self.get_max_t(answerKey, k), self.get_max_f(answerKey, k))

    def get_max_t(self, answerKey, k):
        l = 0
        res = 0
        for r, c in enumerate(answerKey):
            if c == 'F':
                k -= 1
            while k < 0:
                if answerKey[l] == 'F':
                    k += 1
                l += 1
            res = max(res, r - l + 1)
        return res

    def get_max_f(self,  answerKey, k):
        l = 0
        res = 0
        for r, c in enumerate(answerKey):
            if c == 'T':
                k -= 1
            while k < 0:
                if answerKey[l] == 'T':
                    k += 1
                l += 1
            res = max(res , r - l + 1)
        return res

424. 替换后的最长重复字符

给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。
注意：字符串长度 和 k 不会超过 104。

示例 1：
输入：s = “ABAB”, k = 2 输出：4 解释：用两个’A’替换为两个’B’,反之亦然。
示例 2：
输入：s = “AABABBA”, k = 1 输出：4 解释： 将中间的一个’A’替换为’B’,字符串变为 “AABBBBA”。 子串 “BBBB” 有最长重复字母, 答案为 4。
通过次数53,007
提交次数99,712

import collections

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        counter = collections.Counter()
        left = 0
        res = 0
        for right, ch in enumerate(s):
            counter[ch] += 1
            while right - left + 1> counter.most_common(1)[0][1] + k:
                counter[s[left]] -= 1
                left += 1
            res = max(res, right - left + 1)
        return res

关键点是 while right - left + 1> counter.most_common(1)[0][1] + k 用来缩小窗口大小， 缩小的标准是窗口内最多的字母次数 + K 小于窗口大小， 可以类比为 K = 0 求最长重复字母

参考： https://leetcode-cn.com/problems/longest-repeating-character-replacement/solution/tong-guo-ci-ti-liao-jie-yi-xia-shi-yao-shi-hua-don/

438. 找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:
输入: s = “cbaebabacd”, p = “abc” 输出: [0,6] 解释: 起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。 起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。
示例 2:
输入: s = “abab”, p = “ab” 输出: [0,1,2] 解释: 起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。 起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。 起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。

提示:

• 1 <= s.length, p.length <= 3 * 104
• s 和 p 仅包含小写字母

通过次数102,437
提交次数196,670

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        m, n = len(s), len(p)
        cnt_p = Counter(p)
        ans = []
        for i in range(m - n + 1):
            if Counter(s[i:i + n]) == cnt_p:
                ans.append(i)
        return ans


作者：polly-e
链接：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/solution/python-huan-shi-pythonxiu-ya-by-polly-e-hun1/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

import collections

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(s) < len(p): return []
        words = collections.Counter(p)
        res = []
        for i, c in enumerate(s):
            if c in words:
                temp = collections.defaultdict(int)
                start = i
                if i + len(p) <= len(s):
                    for j in range(i, i + len(p)):
                        if s[j] not in words or words[s[j]] == temp[s[j]]:
                            break 
                        temp[s[j]] += 1
                        start += 1
                if start - i == len(p):
                    res.append(i)
        return res

超时解法

487. 最大连续1的个数 II

给定一个二进制数组，你可以最多将 1 个 0 翻转为 1，找出其中最大连续 1 的个数。
示例 1：
输入：[1,0,1,1,0] 输出：4 解释：翻转第一个 0 可以得到最长的连续 1。 当翻转以后，最大连续 1 的个数为 4。

注：

• 输入数组只包含 0 和 1.
• 输入数组的长度为正整数，且不超过 10,000

进阶：
如果输入的数字是作为 无限流 逐个输入如何处理？换句话说，内存不能存储下所有从流中输入的数字。您可以有效地解决吗？

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        left = 0
        res = 0
        k = 1
        for right, n in enumerate(nums):
            if n == 0:
                k -= 1
            while k < 0:
                if nums[left] == 0:
                    k += 1
                left += 1
            res = max(res, right - left + 1)
        return res

567. 字符串的排列

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。

示例 1：
输入：s1 = “ab” s2 = “eidbaooo” 输出：true 解释：s2 包含 s1 的排列之一 (“ba”).
示例 2：
输入：s1= “ab” s2 = “eidboaoo” 输出：false

提示：

• 1 <= s1.length, s2.length <= 104
• s1 和 s2 仅包含小写字母

通过次数128,199
提交次数296,332

import collections

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        word = collections.Counter(s1)
        len_ = len(s1)
        for i in range(len(s2)):
            if word == collections.Counter( s2[i: i + len_]):
                return True
        return False

1052. 爱生气的书店老板

今天，书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客（customers[i]）会进入书店，所有这些顾客都会在那一分钟结束后离开。
在某些时候，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。 当书店老板生气时，那一分钟的顾客就会不满意，不生气则他们是满意的。
书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 X 分钟不生气，但却只能使用一次。
请你返回这一天营业下来，最多有多少客户能够感到满意。

示例：
输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3 输出：16 解释： 书店老板在最后 3 分钟保持冷静。 感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.

提示：

• 1 <= X <= customers.length == grumpy.length <= 20000
• 0 <= customers[i] <= 1000
• 0 <= grumpy[i] <= 1

通过次数48,929
提交次数84,175

解题思路

1.res记录当老板不生气grumpy[R] = 0时，正常情况下客户总数
2.在滑动窗口[L, R]中，当老板生气grumpy[R] = 1时，Sum累加即为当前区间内待挽留客户数
3.当R - L > X时，说明区间[L, R]超出可控范围X，则缩减区间左侧L
4.更新每个区间下待挽留客户数，Max记录最大可挽留客户总数
5.res + Max即为挽留后的最大客户数

作者：victor3290
链接：https://leetcode-cn.com/problems/grumpy-bookstore-owner/solution/hua-dong-chuang-kou-zhao-xun-xfan-wei-ne-qho0/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
        n = len(customers); L = 0; R = 0; Sum = 0; Max = 0; res = 0
        while R < n:
            if grumpy[R] == 0: res += customers[R]  ##正常情况下客户总数
            else: Sum += customers[R]  ##X范围区间内待挽留的客户
            R += 1
            while R - L > X:
                if grumpy[L] == 1: Sum -= customers[L]
                L += 1
            Max = max(Max, Sum)  ##最大可挽留客户数
        return res + Max


作者：victor3290
链接：https://leetcode-cn.com/problems/grumpy-bookstore-owner/solution/hua-dong-chuang-kou-zhao-xun-xfan-wei-ne-qho0/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

187. 重复的DNA序列

所有 DNA 都由一系列缩写为 ‘A’，’C’，’G’ 和 ‘T’ 的核苷酸组成，例如：”ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。
编写一个函数来找出所有目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。

示例 1：
输入：s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT” 输出：[“AAAAACCCCC”,”CCCCCAAAAA”]
示例 2：
输入：s = “AAAAAAAAAAAAA” 输出：[“AAAAAAAAAA”]

提示：

• 0 <= s.length <= 105
• s[i] 为 ‘A’、’C’、’G’ 或 ‘T’

import collections

class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        windows = collections.defaultdict(int)
        res = set()
        for i in range(len(s) - 10 + 1):
            temp = s[i: i + 10]
            windows[temp] += 1
            if windows[temp] > 1:
                res.add(temp)
        return list(res)

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和≥ target的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：
输入：target = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4] 输出：1
示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1] 输出：0

提示：

• 1 <= target <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        left = 0
        res = float("inf")
        temp = 0
        is_found = False
        for right, num in enumerate(nums):
            temp += num
            while temp >= target:
                res = min(res, right - left + 1)
                temp -= nums[left]
                left += 1
                is_found = True
        if is_found:
            return res
        return 0

219. 存在重复元素 II

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。

示例 1:
输入: nums = [1,2,3,1], k = 3 输出: true
示例 2:
输入: nums = [1,0,1,1], k = _1 输出: true
示例 3:
输入: nums = [1,2,3,1,2,3], k = _2 输出: false
通过次数116,261
提交次数274,618

import collections

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        hashmap = collections.defaultdict(int)
        for i, c in enumerate(nums):
            if c in hashmap and abs(hashmap[c] - i) <= k:
                return True
            hashmap[c] = i
        return False

239. 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。

示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7] 解释： 滑动窗口的位置 最大值 ———————- ——- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
示例 2：
输入：nums = [1], k = 1 输出：[1]
示例 3：
输入：nums = [1,-1], k = 1 输出：[1,-1]
示例 4：
输入：nums = [9,11], k = 2 输出：[11]
示例 5：
输入：nums = [4,-2], k = 2 输出：[4]

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• 1 <= k <= nums.length

通过次数206,230
提交次数415,240

题解： https://leetcode-cn.com/problems/sliding-window-maximum/solution/dong-hua-yan-shi-dan-diao-dui-lie-239hua-hc5u/

import collections

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        #以nums = [5,3,4,1]为例子
        q = collections.deque() # 维护一个单调递减的队列
        res = [] 
        for index, n in enumerate(nums):
            # 当滑动窗口不为空，且队列的最后一个值，小于当前要放入的值，则弹出
            # 如果不弹出，则无法维持单调递减，比如窗口为 [5,3] ,当前要放入4, 不弹出则为 [5,3,4] ,那么3对应的index就不是当前最大的值
            while q and nums[q[-1]] < n:
                q.pop()
            #  如果当前的index - 队列头 ，长度大于k,则说明超过了窗口
            q.append(index)
            if q and index - q[0] >= k: 
                q.popleft()

            if index >= k - 1: #表示超过了当前窗口才进行判断
                res.append(nums[q[0]])
        return res

1004. 最大连续1的个数 III

给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。
返回仅包含 1 的最长（连续）子数组的长度。

示例 1：
输入：A = [1,1,1,0,0,0,1,1,1,1,0], K = 2 输出：6 解释： [1,1,1,0,0,1,1,1,1,1,1] 粗体数字从 0 翻转到 1，最长的子数组长度为 6。
示例 2：
输入：A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3 输出：10 解释： [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1] 粗体数字从 0 翻转到 1，最长的子数组长度为 10。

提示：

1. 1 <= A.length <= 20000
2. 0 <= K <= A.length
3. A[i] 为 0 或 1

通过次数70,039
提交次数117,452

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        l = 0 
        res = 0
        for r, n in enumerate(nums):
            if n == 0:
                k -= 1
            while k < 0:
                if nums[l] == 0:
                    k += 1
                l += 1
            res = max(res, r - l + 1)
        return res

1984. 学生分数的最小差值

给你一个 下标从 0 开始 的整数数组 nums ，其中 nums[i] 表示第 i 名学生的分数。另给你一个整数 k 。
从数组中选出任意 k 名学生的分数，使这 k 个分数间 最高分 和 最低分 的 差值 达到 最小化 。
返回可能的 最小差值 。

示例 1：
输入：nums = [90], k = 1 输出：0 解释：选出 1 名学生的分数，仅有 1 种方法： - [90] 最高分和最低分之间的差值是 90 - 90 = 0 可能的最小差值是 0
示例 2：
输入：nums = [9,4,1,7], k = 2 输出：2 解释：选出 2 名学生的分数，有 6 种方法： - [9,4,1,7] 最高分和最低分之间的差值是 9 - 4 = 5 - [9,4,1,7] 最高分和最低分之间的差值是 9 - 1 = 8 - [9,4,1,7] 最高分和最低分之间的差值是 9 - 7 = 2 - [9,4,1,7] 最高分和最低分之间的差值是 4 - 1 = 3 - [9,4,1,7] 最高分和最低分之间的差值是 7 - 4 = 3 - [9,4,1,7] 最高分和最低分之间的差值是 7 - 1 = 6 可能的最小差值是 2

提示：

• 1 <= k <= nums.length <= 1000
• 0 <= nums[i] <= 105

通过次数37,065
提交次数58,673

class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        if k == 1:
            return 0
        nums.sort()
        k -= 1
        ans = float('inf')
        for i in range(len(nums)- k):
            diff = nums[i + k] - nums[i]
            ans = min(ans, diff)
        return ans

1838. 最高频元素的频数

元素的 频数 是该元素在一个数组中出现的次数。
给你一个整数数组 nums 和一个整数 k 。在一步操作中，你可以选择 nums 的一个下标，并将该下标对应元素的值增加 1 。
执行最多 k 次操作后，返回数组中最高频元素的 最大可能频数。

示例 1：
输入：nums = [1,2,4], k = 5 输出：3 解释：对第一个元素执行 3 次递增操作，对第二个元素执 2 次递增操作，此时 nums = [4,4,4] 。 4 是数组中最高频元素，频数是 3 。
示例 2：
输入：nums = [1,4,8,13], k = 5 输出：2 解释：存在多种最优解决方案： - 对第一个元素执行 3 次递增操作，此时 nums = [4,4,8,13] 。4 是数组中最高频元素，频数是 2 。 - 对第二个元素执行 4 次递增操作，此时 nums = [1,8,8,13] 。8 是数组中最高频元素，频数是 2 。 - 对第三个元素执行 5 次递增操作，此时 nums = [1,4,13,13] 。13 是数组中最高频元素，频数是 2 。
示例 3：
输入：nums = [3,9,6], k = 2 输出：1

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105
• 1 <= k <= 105

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        nums.sort()
        ans = 1
        l = 0
        temp = 0
        for r in range(1, len(nums)):
            temp += (nums[r] - nums[r- 1]) * (r - l)
            while temp > k:
                temp -= nums[r] - nums[l]
                l+= 1
            ans = max(ans, r- l + 1)
        return ans