# 题单（右边的数字是题目难度） > 来源[灵茶山艾府](https://space.bilibili.com/206214) ## 滑窗问题 ### 定长滑动窗口 over !!! 😊

### 不定长滑动窗口（求最长/最大）剩 1 个

### 不定长滑动窗口（求最短/最小）over !!! 😊

### 不定长滑动窗口（求子数组个数）over !!! 😊

### 多指针滑动窗口

## 二分答案 ### 二分答案

### 最小化最大值

### 最大化最小值

### 第 K 小/大（部分题目也可以用堆解决）

# 狠狠做题 ## 滑动窗口问题 ### 定长滑动窗口 #### [1456. 定长子串中元音的最大数目](https://leetcode.cn/problems/maximum-number-of-vowels-in-a-substring-of-given-length/) ```py class Solution: def maxVowels(self, s: str, k: int) -> int: vowel = {} vowel['a'] = 1 vowel['e'] = 1 vowel['i'] = 1 vowel['o'] = 1 vowel['u'] = 1 i, ans, cnt = 0, 0, 0 for j, x in enumerate(s): cnt += 1 if x in vowel else 0 if j - i + 1 > k: cnt -= 1 if s[i] in vowel else 0 i += 1 ans = max(ans, cnt) return ans ``` #### [2269. 找到一个数字的 K 美丽值](https://leetcode.cn/problems/find-the-k-beauty-of-a-number/) ```py class Solution: def divisorSubstrings(self, num: int, k: int) -> int: i, ans = 0, 0 s = str(num) for j, x in enumerate(s): if j - i + 1 > k: i += 1 if j - i + 1 == k and int(s[i:j + 1]) != 0 and num % int(s[i:j + 1]) == 0: ans += 1 return ans ``` #### [1984. 学生分数的最小差值](https://leetcode.cn/problems/minimum-difference-between-highest-and-lowest-of-k-scores/) ```py class Solution: def minimumDifference(self, nums: List[int], k: int) -> int: nums.sort() i, ans = 0, inf for j, x in enumerate(nums): while j - i + 1 > k: i += 1 if j - i + 1 == k: ans = min(ans, x - nums[i]) return ans ``` #### [643. 子数组最大平均数 I](https://leetcode.cn/problems/maximum-average-subarray-i/) ```py class Solution: def findMaxAverage(self, nums: List[int], k: int) -> float: i, ans, cnt = 0, -inf, 0 for j, x in enumerate(nums): cnt += x while j - i + 1 > k: cnt -= nums[i] i += 1 if j - i + 1 == k: ans = max(ans, cnt / k) return ans ``` #### [1343. 大小为 K 且平均值大于等于阈值的子数组数目](https://leetcode.cn/problems/number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold/) ```py class Solution: def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int: i, ans, cnt = 0, 0, 0 for j, x in enumerate(arr): cnt += x while j - i + 1 > k: cnt -= arr[i] i += 1 if j - i + 1 == k and cnt / k >= threshold: ans += 1 return ans ``` #### [2090. 半径为 k 的子数组平均值](https://leetcode.cn/problems/k-radius-subarray-averages/description/) ```py class Solution: def getAverages(self, nums: List[int], k: int) -> List[int]: n = len(nums) i, ans, cnt = 0, [-1 for _ in range(n)], 0 if n < 2 * k + 1: return ans for j, x in enumerate(nums): cnt += x if j >= k: if j - i + 1 > k * 2 + 1: cnt -= nums[i] i += 1 if j - i + 1 == k * 2 + 1: ans[(j + i) >> 1] = cnt // (k * 2 + 1) return ans ``` #### [2379. 得到 K 个黑块的最少涂色次数](https://leetcode.cn/problems/minimum-recolors-to-get-k-consecutive-black-blocks/) ```py class Solution: def minimumRecolors(self, blocks: str, k: int) -> int: vis = {} vis['W'], vis['B'] = 1, 0 i, ans, cnt = 0, inf, 0 for j, x in enumerate(blocks): cnt += vis[x] if j - i + 1 > k: cnt -= vis[blocks[i]] i += 1 if j - i + 1 == k: ans = min(ans, cnt) return ans ``` #### [1052. 爱生气的书店老板](https://leetcode.cn/problems/grumpy-bookstore-owner/) > 求数组里把某一个长度为 minute 的区间都改成 0 会造成的差值（增长）最大，只需要使用这个差值加上原有的大小即可 ```py class Solution: def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int: i, ans, cnt, max_diff = 0, 0, 0, 0 for j, x in enumerate(customers): cnt += x if grumpy[j] else 0 ans += 0 if grumpy[j] else x while j - i + 1 > minutes: cnt -= customers[i] if grumpy[i] else 0 i += 1 if j - i + 1 == minutes: max_diff = max(max_diff, cnt) return ans + max_diff ``` #### [2841. 几乎唯一子数组的最大和](https://leetcode.cn/problems/maximum-sum-of-almost-unique-subarray/) ```py class Solution: def maxSum(self, nums: List[int], m: int, k: int) -> int: # 一边求唯一子数组数量，一边求最大值 cnt = defaultdict(int) i, ans, s = 0, 0, 0 for j, x in enumerate(nums): cnt[x] = cnt[x] + 1 s += x if j - i + 1 > k: cnt[nums[i]] -= 1 s -= nums[i] if cnt[nums[i]] == 0: del cnt[nums[i]] i += 1 if j - i + 1 == k and len(cnt) >= m: ans = max(ans, s) return ans if ans != 0 else 0 ``` #### [2461. 长度为 K 子数组中的最大和](https://leetcode.cn/problems/maximum-sum-of-distinct-subarrays-with-length-k/) ```py class Solution: def maximumSubarraySum(self, nums: List[int], k: int) -> int: # 维护map && 子数组和 i, ans, s, cnt = 0, 0, 0, defaultdict(int) for j, x in enumerate(nums): s += x cnt[x] += 1 if j - i + 1 > k: cnt[nums[i]] -= 1 s -= nums[i] if cnt[nums[i]] == 0: del cnt[nums[i]] i += 1 if j - i + 1 == k and len(cnt) == k: ans = max(ans, s) return ans ``` #### [1423. 可获得的最大点数](https://leetcode.cn/problems/maximum-points-you-can-obtain-from-cards/) ```py class Solution: def maxScore(self, cardPoints: List[int], k: int) -> int: # 防止维护两端, 直接反着做, 求最小子数组和 sumn, n = sum(cardPoints), len(cardPoints) k = n - k if k == 0: return sumn ans, i, cnt = sumn, 0, 0 for j, x in enumerate(cardPoints): cnt += x while j - i + 1 > k: cnt -= cardPoints[i] i += 1 if j - i + 1 == k: ans = min(ans, cnt) return sumn - ans ``` #### [2134. 最少交换次数来组合所有的 1 II](https://leetcode.cn/problems/minimum-swaps-to-group-all-1s-together-ii/) ```py class Solution: def minSwaps(self, nums: List[int]) -> int: # 求 1 最长长度 k = sum(nums) nums += nums # 求 k 能覆盖的最长的 1 的窗口 i, ans, cnt = 0, 0, 0 for j, x in enumerate(nums): cnt += x while j - i + 1 > k: cnt -= nums[i] i += 1 if j - i + 1 == k: ans = max(ans, cnt) return k - ans ``` #### [2653. 滑动子数组的美丽值](https://leetcode.cn/problems/sliding-subarray-beauty/) ```py class Solution: def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]: # 求数组区间最小值 n = len(nums) i, cnt = 0, defaultdict(int) ans = [] for j, num in enumerate(nums): # 判断窗口长度 cnt[num] += 1 while j - i + 1 > k: cnt[nums[i]] -= 1 if cnt[nums[i]] == 0: del cnt[nums[i]] i += 1 t = x if j - i + 1 == k: for a in range(-50, 51): if a in cnt: if cnt[a] >= t: ans.append(min(0, a)) break else: t -= cnt[a] return ans ``` #### [567. 字符串的排列](https://leetcode.cn/problems/permutation-in-string/) ```py class Solution: def checkInclusion(self, s1: str, s2: str) -> bool: # 每个窗口都判断是否包含所有 s1 i, cnt, n = 0, Counter(), len(s1) s = Counter(s1) for j, x in enumerate(s2): cnt[x] += 1 while j - i + 1 > n: cnt[s2[i]] -= 1 if cnt[s2[i]] == 0: del cnt[s2[i]] i += 1 if cnt.items() == s.items(): return True return False ``` #### [438. 找到字符串中所有字母异位词](https://leetcode.cn/problems/find-all-anagrams-in-a-string/) ```py class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: k = len(p) origin = Counter(p) i, ans, cnt = 0, [], Counter() for j, x in enumerate(s): cnt[x] += 1 if j - i + 1 > k: cnt[s[i]] -= 1 if cnt[s[i]] == 0: del cnt[s[i]] i += 1 if j - i + 1 == k and origin.items() == cnt.items(): ans.append(i) return ans ``` #### [2156. 查找给定哈希值的子串](https://leetcode.cn/problems/find-substring-with-given-hash-value/) ```py class Solution: def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str: nums = [(ord(x) - ord('a') + 1) for x in s] n = len(nums) i, cnt, ans = n - 1, 0, n - 1 # 由于正向减去再除去不一定得到的是整数，会有误差 # 反向乘法会好些 """ m = power ** (k - 1)% modulo 这一句拿出来算，我在里面算，超时了好多次🥲 """ m = power ** (k - 1)% modulo for j in range(n - 1, -1, -1): if i - j + 1 > k: cnt = (cnt - (nums[i] * m) % modulo) i -= 1 cnt = ((cnt * power) % modulo + nums[j] % modulo) % modulo if i - j + 1 == k and cnt == hashValue: ans = j return s[ans:ans + k] ``` ### 不定长滑动窗口（求最长/最大） #### [3. 无重复字符的最长子串](https://leetcode.cn/problems/longest-substring-without-repeating-characters/) ```py class Solution: def lengthOfLongestSubstring(self, s: str) -> int: i, cnt = 0, defaultdict(int) ans = 0 for j, x in enumerate(s): while x in cnt: cnt[s[i]] -= 1 if cnt[s[i]] == 0: del cnt[s[i]] i += 1 cnt[x] += 1 ans = max(ans, j - i + 1) return ans ``` #### [1493. 删掉一个元素以后全为 1 的最长子数组](https://leetcode.cn/problems/longest-subarray-of-1s-after-deleting-one-element/) ```py class Solution: def longestSubarray(self, nums: List[int]) -> int: i, cnt = 0, defaultdict(int) ans = 0 for j, x in enumerate(nums): cnt[x] += 1 while cnt[1] < j - i: cnt[nums[i]] -= 1 if cnt[nums[i]] == 0: del cnt[nums[i]] i += 1 ans = max(ans, j - i + 1) return ans - 1 ``` #### [904. 水果成篮](https://leetcode.cn/problems/fruit-into-baskets/) ```py class Solution: def totalFruit(self, fruits: List[int]) -> int: i, cnt = 0, defaultdict(int) ans = 0 for j, x in enumerate(fruits): cnt[x] += 1 while len(cnt) > 2: cnt[fruits[i]] -= 1 if cnt[fruits[i]] == 0: del cnt[fruits[i]] i += 1 ans = max(ans, j - i + 1) return ans ``` #### [1695. 删除子数组的最大得分](https://leetcode.cn/problems/maximum-erasure-value/) ```py class Solution: def maximumUniqueSubarray(self, nums: List[int]) -> int: cnt = defaultdict(int) i, ans, s = 0, 0, 0 for j, x in enumerate(nums): while x in cnt: cnt[nums[i]] -= 1 s -= nums[i] if cnt[nums[i]] == 0: del cnt[nums[i]] i += 1 cnt[x] += 1 s += x ans = max(ans, s) return ans ``` #### [2841. 几乎唯一子数组的最大和](https://leetcode.cn/problems/maximum-sum-of-almost-unique-subarray/) ```py class Solution: def maxSum(self, nums: List[int], m: int, k: int) -> int: i, ans, cnt, s = 0, 0, defaultdict(int), 0 for j, x in enumerate(nums): cnt[x] += 1 s += x while j - i + 1 > k: cnt[nums[i]] -= 1 s -= nums[i] if cnt[nums[i]] == 0: del cnt[nums[i]] i += 1 if j - i + 1 == k and len(cnt) >= m: ans = max(ans, s) return ans ``` #### [2024. 考试的最大困扰度](https://leetcode.cn/problems/maximize-the-confusion-of-an-exam/) ```py class Solution: def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int: def getAns(s: str) -> int: i, ans, cnt, l = 0, 0, Counter(), 0 for j, x in enumerate(answerKey): cnt[x] += 1 if x == s else 0 while cnt[x] > k: cnt[answerKey[i]] -= 1 if answerKey[i] == s else 0 if cnt[answerKey[i]] == 0: del cnt[answerKey[i]] i += 1 ans = max(ans, j - i + 1) return ans return max(getAns('T'), getAns('F')) ``` #### [1004. 最大连续 1 的个数 III](https://leetcode.cn/problems/max-consecutive-ones-iii/) ```py class Solution: def longestOnes(self, nums: List[int], k: int) -> int: # 求存在一个最长的子数组，子数组中最多只能有 k 个0 i, ans, cnt = 0, 0, defaultdict(int) for j, x in enumerate(nums): cnt[x] += 1 while cnt[0] > k: cnt[nums[i]] -= 1 if cnt[nums[i]] == 0: del cnt[nums[i]] i += 1 ans = max(ans, j - i + 1) return ans ``` #### [1438. 绝对差不超过限制的最长连续子数组](https://leetcode.cn/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/) ```py from sortedcontainers import SortedList class Solution: def longestSubarray(self, nums: List[int], limit: int) -> int: # 使用有序数组, 插入 log(n) i, ans, cnt = 0, 0, SortedList() for j, x in enumerate(nums): cnt.add(x) while cnt[-1] - cnt[0] > limit: cnt.remove(nums[i]) i += 1 ans = max(ans, j - i + 1) return ans ``` #### [2401. 最长优雅子数组](https://leetcode.cn/problems/longest-nice-subarray/description/) > 位运算的集合思想结合滑动窗口 > > 位运算技巧: [技巧](https://leetcode.cn/circle/discuss/CaOJ45/) ```py class Solution: def longestNiceSubarray(self, nums: List[int]) -> int: # 按照按位与和集合的特性做 # https://leetcode.cn/circle/discuss/CaOJ45/ # 如果没用交集才能为0 i, ans, _or = 0, 0, 0 for j, x in enumerate(nums): while _or & x != 0: # 删除集合中的子集 nums[i] _or ^= nums[i] i += 1 # 加入集合 _or |= x ans = max(ans, j - i + 1) return ans ``` #### [1658. 将 x 减到 0 的最小操作数](https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/) ```py class Solution: def minOperations(self, nums: List[int], x: int) -> int: # 求最短和为 x 的两端子数组 # 求最长和为 sum - x 的子数组 i, ans, cnt = 0, -1, 0 x = sum(nums) - x if x < 0: return -1 for j, num in enumerate(nums): cnt += num while cnt > x: cnt -= nums[i] i += 1 if cnt == x: ans = max(ans, j - i + 1) return (len(nums) - ans) if ans != -1 else -1 ``` #### [1838. 最高频元素的频数](https://leetcode.cn/problems/frequency-of-the-most-frequent-element/) > 有点难，不过确实好题 🥲 - 排序 + 滑动窗口做法为了保持面积好求, 先进行排序。窗口每次向右边移动, 整体操作次数都得重复加上 $(nums[r] - nums[r - 1]) * (r - l)$, `l`、`r`为窗口左、右边界。窗口左边界右移的之前, 整体操作次数减去 $nums[r] - nums[l]$, 再右移 ![](/public/images/2023-10-16_09-08-28_185e06db-6e3e-4002-8579-a28c5223a6df.png) ```py class Solution: def maxFrequency(self, nums: List[int], k: int) -> int: # 排序 + 窗口做法 n = len(nums) nums.sort() i, ans, s = 0, 0, 0 # 灵活求 s for j, x in enumerate(nums): # 把前面的左右都需要加上的差值都算上 s += (j - i) * (x - nums[j - 1]) while s > k: # 减去差值 s -= x - nums[i] i += 1 ans = max(ans, j - i + 1) return ans ``` - 排序 + 前缀和 + 二分做法 ![](/public/images/2023-10-16_11-44-07_2f446b83-aee9-4920-bfb1-fb2778963fc8.png) ```py class Solution: def maxFrequency(self, nums: List[int], k: int) -> int: n = len(nums) # 排序 nums.sort() # 对每个右边界找最左边界满足区间操作数和 <= k left, ans, cnt = 0, 0, 0 s = [0 for _ in range(n + 1)] # 先求前缀和 for i in range(1, n + 1): s[i] = s[i - 1] + nums[i - 1] for right, x in enumerate(nums): l, r = 0, right while l < r: mid = l + r >> 1 # 找最左边 if x * (right - mid + 1) - (s[right + 1] - s[mid]) > k: l = mid + 1 else: r = mid if x * (right - l + 1) - (s[right + 1] - s[l]) <= k: ans = max(ans, right - l + 1) return ans ``` #### [2831. 找出最长等值子数组](https://leetcode.cn/problems/find-the-longest-equal-subarray/) - 滑动窗口做法$O(n)$ > 对每个单独的数字进行滑动窗口遍历 ```py class Solution: def longestEqualSubarray(self, nums: List[int], k: int) -> int: # 首先把相同的数字分组 n = len(nums) idx = [[] for _ in range(n + 1)] for i, x in enumerate(nums): idx[x].append(i) ans = 0 # 遍历每个窗口 for i in idx: # 当前窗口的最长的连续长度 l = 0 for r, x in enumerate(i): # 当前窗口真实长度 - 窗口中相同数字的长度 while (x - i[l] + 1) - (r - l + 1) > k: l += 1 ans = max(ans, r - l + 1) return ans ``` - 二分答案做法$O(nlogn)$ ```py class Solution: def longestEqualSubarray(self, nums: List[int], k: int) -> int: n = len(nums) l, r = 1, n # 判断是否有连续 m 个元素相等的子数组 def check(m: int) -> bool: i, ans, cnt = 0, 0, defaultdict(int) for j, x in enumerate(nums): cnt[x] += 1 # 有 m 个相同, 则窗口长度最大为 k + m while j - i + 1 > k + m: cnt[nums[i]] -= 1 if cnt[nums[i]] == 0: del cnt[nums[i]] i += 1 # 如果当前数量 >= m 即可 if cnt[x] == m: return True return False # 二分答案, 查找最大的连续相同的数量 while l < r: mid = l + r + 1 >> 1 if check(mid): l = mid else: r = mid - 1 return r ``` #### [2106. 摘水果](https://leetcode.cn/problems/maximum-fruits-harvested-after-at-most-k-steps/) > 求能走到的最左边的坐标`left`为`starPos - k`, 最右边的坐标`right`为`starPos + k`, 遍历`right`从`starPos - k`到`starPos + k`, 然后根据方向来判断**往左走再往右走**和**往右走再往左走**的长度够不够 > > 假设位置不超过`startPos`的最近水果在`fruits[right][0]`, 那么当`right`增加时, `left`不可能减少, 有单调性, 因此可以用同向双指针（滑动窗口）解决。 > > ![](/public/images/2023-10-16_14-14-46_3674f0f2-774f-4ef6-be55-71ae573a6ee0.png) > > 当$frults[right][0] - starPos + frults[right][0] - frults[left][0] > k$时, 说明先向右再向左的**步数**过大 > > 当$startPos − fruits[left][0] + fruits[right][0] − fruits[left][0] > k$时, 说明先向左再向右的**步数**过大 > > 当上面两个方向都不满足, 说明是`left`需要增大了 ```py class Solution: def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int: # 枚举能走到的最左边 left = -1 for i, x in enumerate(fruits): if x[0] >= startPos - k: left = i break if left == -1: return 0 ans, s = 0, 0 for right, p in fruits[left:]: if right > startPos + k: break s += p """ 判断走的总距离是否合法, 无论什么方向, 只要走的最右边增加, 最左边也只会增加 """ while right * 2 - startPos - fruits[left][0] > k and \ startPos - fruits[left][0] * 2 + right > k: s -= fruits[left][1] left += 1 ans = max(ans, s) return ans ``` ### 不定长滑动窗口（求最短/最小） #### [209. 长度最小的子数组](https://leetcode.cn/problems/minimum-size-subarray-sum/) ```py class Solution: def minSubArrayLen(self, target: int, nums: List[int]) -> int: i, cnt, ans = 0, 0, 0x3f3f3f3f for j, x in enumerate(nums): cnt += x while cnt >= target: ans = min(ans, j - i + 1) cnt -= nums[i] i += 1 return ans if ans != 0x3f3f3f3f else 0 ``` #### [1234. 替换子串得到平衡字符串](https://leetcode.cn/problems/replace-the-substring-for-balanced-string/) > 难想出来, 求最短的窗口能保证窗口外的字母数量均 <= m ```py class Solution: def balancedString(self, s: str) -> int: n = len(s) m = n // 4 # 求最短的窗口, 使得窗口外的所有字母都能 <= m l, ans, cnt = 0, inf, Counter(s) if all(cnt[x] == m for x in "QWER"): return 0 for r, c in enumerate(s): # 保持窗口外面的所有的都不超过m cnt[c] -= 1 while all(cnt[x] <= m for x in "QWER"): # 满足即可增大左边，减小窗口 ans = min(ans, r - l + 1) cnt[s[l]] += 1 l += 1 return ans ``` #### [1574. 删除最短的子数组使剩余数组有序](https://leetcode.cn/problems/shortest-subarray-to-be-removed-to-make-array-sorted/) - 滑动窗口做法$O(n)$ ```py class Solution: def findLengthOfShortestSubarray(self, arr: List[int]) -> int: n = len(arr) right = n - 1 while right > 0: if arr[right] < arr[right - 1]: break right -= 1 if right == 0: return 0 ans = right # 枚举最左边来移动删除窗口的右边界 for left, x in enumerate(arr): if left != 0 and arr[left] < arr[left - 1]: break # 右边界必须大于左边 while right < n and arr[left] > arr[right]: right += 1 ans = min(ans, right - left - 1) left += 1 return ans ``` - 双指针二分做法$O(nlogn)$ ```py class Solution: def findLengthOfShortestSubarray(self, arr: List[int]) -> int: # 删除子数组使得有序 # 将数组分成三部分, 左中右 # 左边和右边为长度 [0,n]的有序子数组 # 先找左右的起点移动 n = len(arr) left, right = 0, n - 1 while left < n - 1: if arr[left] > arr[left + 1]: break left += 1 while right > 0: if arr[right] < arr[right - 1]: break right -= 1 if right == 0 or left == n - 1: return 0 ans = min(n - left - 1, right) for i in range(left + 1): # 在右边找最适合左边的 # 二分 l, r = right, n - 1 while l < r: mid = l + r >> 1 if (arr[mid] < arr[i]): l = mid + 1 else: r = mid # print(i, l, arr[i], arr[l]) if (arr[l] >= arr[i]): ans = min(ans, l - i - 1) return ans ``` #### [76. 最小覆盖子串](https://leetcode.cn/problems/minimum-window-substring/) > 难想出来的滑动窗口，用目标串和窗口里包含目标串的长度来当窗口 ```py class Solution: def minWindow(self, s: str, t: str) -> str: left, ans, cnt = 0, len(s), defaultdict(int) for x in t: cnt[x] += 1 l = len(cnt) idx = len(s) for right, x in enumerate(s): if x in t: if cnt[x] == 1: l -= 1 cnt[x] -= 1 print(left, right, s[left], x, ans, idx, l) # 当前窗口满足了, 开始缩小范围 while l <= 0: # 跳过不影响的点 while s[left] not in t: left += 1 if l <= 0 and ans >= right - left + 1: ans = right - left + 1 idx = left if s[left] in t: if cnt[s[left]] == 0: l += 1 cnt[s[left]] += 1 left += 1 return s[idx:idx + ans] ``` ### 不定长滑动窗口（求子数组个数） over !!! 😊 #### [2799. 统计完全子数组的数目](https://leetcode.cn/problems/count-complete-subarrays-in-an-array/) > 枚举右端点计算每个右端点可以算进去的最右边的左端点 > > $ans += left$ 即可 ```py class Solution: def countCompleteSubarrays(self, nums: List[int]) -> int: left = ans = 0 cnt = defaultdict(int) n = len(set(nums)) # 枚举右端点 for right, x in enumerate(nums): cnt[x] += 1 while len(cnt) == n: cnt[nums[left]] -= 1 if cnt[nums[left]] == 0: del cnt[nums[left]] left += 1 # 累加当前右端点能接受的左端点个数 ans += left return ans ``` #### [713. 乘积小于 K 的子数组](https://leetcode.cn/problems/subarray-product-less-than-k/) ```py class Solution: def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int: left, ans, mul = 0, 0, 1 if min(nums) >= k: return 0 for right, x in enumerate(nums): mul *= x while mul >= k: mul //= nums[left] left += 1 # 当前区间的数的种类 ans += right - left + 1 return ans ``` #### [1358. 包含所有三种字符的子字符串数目](https://leetcode.cn/problems/number-of-substrings-containing-all-three-characters/) ```py class Solution: def numberOfSubstrings(self, s: str) -> int: left, ans, cnt = 0, 0, defaultdict(int) for right, x in enumerate(s): cnt[x] += 1 while len(cnt) >= 3: cnt[s[left]] -= 1 if cnt[s[left]] == 0: del cnt[s[left]] left += 1 ans += left return ans ``` #### [2302. 统计得分小于 K 的子数组数目](https://leetcode.cn/problems/count-subarrays-with-score-less-than-k/) ```py class Solution: def countSubarrays(self, nums: List[int], k: int) -> int: left = ans = 0 s = 0 for right, x in enumerate(nums): s = (((s // (right - left)) if right != left else 0) + x) * (right - left + 1) while s >= k: s = ((s // (right - left + 1)) - nums[left]) * (right - left) left += 1 ans += right - left + 1 return ans ``` > 可以优化计算, 不需要每次都算出来子数组的值，只需要和就行 ```py class Solution: def countSubarrays(self, nums: List[int], k: int) -> int: left = ans = 0 s = 0 for right, x in enumerate(nums): s += x while s * (right - left + 1) >= k: s -= nums[left] left += 1 ans += right - left + 1 return ans ``` #### [2537. 统计好子数组的数目](https://leetcode.cn/problems/count-the-number-of-good-subarrays/) ```py class Solution: def countGood(self, nums: List[int], k: int) -> int: left, ans = 0, 0 cnt = defaultdict(int) gs = 0 for right, x in enumerate(nums): gs += cnt[x] cnt[x] += 1 while gs >= k: gs -= cnt[nums[left]] - 1 cnt[nums[left]] -= 1 left += 1 ans += left return ans ``` #### [2762. 不间断子数组](https://leetcode.cn/problems/continuous-subarrays/) ```py from sortedcontainers import SortedList class Solution: def continuousSubarrays(self, nums: List[int]) -> int: left, ans = 0, 0 q = SortedList() for right, x in enumerate(nums): q.add(x) while q[-1] - q[0] > 2: q.discard(nums[left]) left += 1 ans += right - left + 1 return ans ``` ### 多指针滑动窗口 #### [930. 和相同的二元子数组](https://leetcode.cn/problems/binary-subarrays-with-sum/) ```py class Solution: def numSubarraysWithSum(self, nums: List[int], goal: int) -> int: left = left2 = ans = 0 cnt1 = cnt2 = 0 for right, x in enumerate(nums): cnt1 += x cnt2 += x # 走到 cnt == goal 的左边界 while cnt1 > goal and left <= right: cnt1 -= nums[left] left += 1 # 左边界的最右条件 while cnt2 >= goal and left2 <= right: cnt2 -= nums[left2] left2 += 1 # [left, left2)为符合的边界 ans += left2 - left return ans ``` #### [1248. 统计「优美子数组」](https://leetcode.cn/problems/count-number-of-nice-subarrays/) ```py class Solution: def numberOfSubarrays(self, nums: List[int], k: int) -> int: left = left2 = ans = 0 cnt = cnt2 = 0 for right, x in enumerate(nums): cnt += x % 2 cnt2 += x % 2 while cnt > k and left <= right: cnt -= nums[left] % 2 left += 1 while cnt2 >= k and left2 <= right: cnt2 -= nums[left2] % 2 left2 += 1 ans += left2 - left return ans ``` #### [1712. 将数组分成三个子数组的方案数](https://leetcode.cn/problems/ways-to-split-array-into-three-subarrays/) - 划分区域的灵活变化 ```py class Solution: def waysToSplit(self, nums: List[int]) -> int: n = len(nums) ans = 0 MOD = 10**9 + 7 for i in range(1, n): nums[i] += nums[i - 1] l, m, r = 0, 1, 1 # 第一条分界线最多到 nums[l] * 3 <= nums[n - 1] while l < n - 2 and nums[l] * 3 <= nums[n - 1]: m = max(m, l + 1) # 第二条线最左 while (m < n - 1 and nums[m] < nums[l] * 2): m += 1 # 第二条线最右边 while (r < n - 2 and nums[r + 1] - nums[l] <= nums[n - 1] - nums[r + 1]): r += 1 ans = (ans + r - m + 1) % MOD l += 1 return ans ``` ## 二分答案 ### 二分答案 #### [1283. 使结果不超过阈值的最小除数](https://leetcode.cn/problems/find-the-smallest-divisor-given-a-threshold/) ```py class Solution: def smallestDivisor(self, nums: List[int], threshold: int) -> int: l, r = 1, max(nums) def check(x: int) -> bool: return sum((i // x + 1 if i % x != 0 else i // x ) for i in nums) > threshold while l < r: mid = l + r >> 1 if check(mid): l = mid + 1 else: r = mid return l ``` #### [2187. 完成旅途的最少时间](https://leetcode.cn/problems/minimum-time-to-complete-trips/) ```py class Solution: def minimumTime(self, time: List[int], totalTrips: int) -> int: l, r = 1, max(time) * totalTrips def check(x: int) -> bool: return sum((x // i) for i in time) < totalTrips while l < r: mid = l + r >> 1 if check(mid): l = mid + 1 else: r = mid return l ``` #### [2226. 每个小孩最多能分到多少糖果](https://leetcode.cn/problems/maximum-candies-allocated-to-k-children/) ```cpp typedef long long LL; class Solution { public: int maximumCandies(vector& candies, long long k) { LL max_n = *max_element(candies.begin(), candies.end()); LL l = 1, r = max_n; auto check = [&](LL x) { // 把所有的大于 x 的数分出来若干个 x，总数量 >= k，就可以 LL cnt = 0; for (auto candy : candies) { cnt = cnt + (LL)(candy / x); if (cnt >= k) return true; } return cnt >= k; }; while (l < r) { LL mid = (l + r + 1) >> 1; if (check(mid)) l = mid; else r = mid - 1; } return check(r) ? r : 0; } }; ``` #### [1870. 准时到达的列车最小时速](https://leetcode.cn/problems/minimum-speed-to-arrive-on-time/) ```cpp class Solution { public: int minSpeedOnTime(vector& dist, double hour) { int n = dist.size(); auto check = [&](int x){ double cnt = 0.0; for (int i = 0; i < n - 1; ++ i) { cnt += (dist[i] - 1) / x + 1; if (cnt > hour) { return false; } } cnt += (double)dist.back() / x; return cnt <= hour; }; if (n - 1 > hour) return -1; int l = 1, r = 10000000; while (l < r) { int mid = (r + l) >> 1; if (!check(mid)) l = mid + 1; else r = mid; } return check(l) ? l : -1; } }; ``` #### [1011. 在 D 天内送达包裹的能力](https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/description/) ```cpp class Solution { public: int shipWithinDays(vector& ws, int days) { int sum = accumulate(ws.begin(), ws.end(), 0); int l = *max_element(ws.begin(), ws.end()), r = sum; auto check = [&](int mid) { int sum = 0, cnt = 0; for (int i : ws) { if (sum + i > mid) { sum = 0; cnt += 1; } sum += i; } cnt += (sum > 0); return cnt <= days; }; while (l < r) { int mid = (l + r) >> 1; if (check(mid)) r = mid; else l = mid + 1; } return check(l) ? l : -1; } }; ``` #### [875. 爱吃香蕉的珂珂](https://leetcode.cn/problems/koko-eating-bananas/) ```cpp class Solution { public: int minEatingSpeed(vector& piles, int h) { int l = 1, r = *max_element(piles.begin(), piles.end()); auto check = [&](int mid) { int sum = 0; for (int pile : piles) // 向上取整 sum += (pile - 1) / mid + 1; return sum <= h; }; while (l < r) { int mid = (l + r) >> 1; if (check(mid)) r = mid; else l = mid + 1; } return check(l) ? l : -1; } }; ``` #### [1898. 可移除字符的最大数目](https://leetcode.cn/problems/maximum-number-of-removable-characters/) ```cpp class Solution { public: int maximumRemovals(string s, string p, vector& removable) { int l = 0, r = removable.size(); auto check = [&](int mid) { string temp = s; for (int i = 0; i < mid; ++ i) temp.replace(removable[i], 1, " "); int i = 0, j = 0; while (i < s.size() && j < p.size()) { if (temp[i] == ' ') ++ i; else if (temp[i] == p[j]) ++ i, ++ j; else ++ i; } return j == p.size(); }; while (l < r) { int mid = (l + r + 1) >> 1; if (check(mid)) l = mid; else r = mid - 1; } return check(r) ? r : 0; } }; ``` #### [1482. 制作 m 束花所需的最少天数](https://leetcode.cn/problems/minimum-number-of-days-to-make-m-bouquets/) ```cpp class Solution { public: int minDays(vector& bloomDay, int m, int k) { int l = *min_element(bloomDay.begin(), bloomDay.end()), r = *max_element(bloomDay.begin(), bloomDay.end()); auto check = [&](int mid){ int cnt = 0; int along = 0, i = 0; while (i < bloomDay.size()) { if (bloomDay[i] <= mid) ++ along; else along = 0; if (along >= k) { along = 0; ++ cnt; } if(cnt >= m) return true; ++ i; } return cnt >= m; }; while (l < r) { int mid = (l + r) >> 1; if (check(mid)) r = mid; else l = mid + 1; } return check(l) ? l : -1; } }; ``` #### [1642. 可以到达的最远建筑](https://leetcode.cn/problems/furthest-building-you-can-reach/) ```cpp class Solution { public: int furthestBuilding(vector& heights, int bricks, int ladders) { // 差分 int n = heights.size(); for (int i = 0; i < n - 1; ++ i) if (heights[i] < heights[i + 1]) heights[i] = heights[i + 1] - heights[i]; else heights[i] = 0; auto check = [&](int mid) { priority_queue, less> heap(heights.begin(), heights.begin() + mid); // 先把大的用梯子 int _ladders = ladders, _bricks = bricks; while (!heap.empty() && _ladders --) heap.pop(); int sum = 0; while (!heap.empty()) sum += heap.top(), heap.pop(); return sum <= _bricks; }; int l = 0, r = n - 1; while (l < r) { int mid = (l + r + 1) >> 1; if (check(mid)) l = mid; else r = mid - 1; } return check(r) ? r : -1; } }; ```

leetcode题单