指针的本质是映射，使用一个地址保留我们想知道的东西。
滑动窗口是双指针思想的一种实现，使用l, r两个指针来维护一个数组的子序列。
滑动窗口问题可以分为两类，一类是固定大小的滑动窗口，一类是变长滑动窗口。
定长滑动窗口：求区间最大
不定长滑动窗口: 求最长，最短，子数组个数。
变长滑动窗口求最长最短问题
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
n = len(nums)
res = inf
s = 0
left = 0
for right, x in enumerate(nums):
s += x
while s - nums[left] >= target:
s -= nums[left]
left += 1
if s >= target:
res = min(res, right - left + 1)
return res if res <= n else 0
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
n = len(s)
cnt = Counter()
left = 0
res = 0
for right, x in enumerate(s):
cnt[s[right]] += 1
while cnt[s[right]] > 1:
cnt[s[left]] -= 1
left += 1
res = max(res, right - left + 1)
return res
class Solution:
def longestSubarray(self, nums: List[int]) -> int:
n = len(nums)
res = 0
left = 0
cnt = 0
for right, x in enumerate(nums):
if x == 0:
cnt += 1
while cnt > 1:
if nums[left] == 0:
cnt -= 1
left += 1
res = max(res, right - left)
return res
class Solution:
def totalFruit(self, fruits: List[int]) -> int:
n = len(fruits)
left = 0
res = 0
c = Counter()
cnt = 0
for right, x in enumerate(fruits):
c[fruits[right]] += 1
if c[fruits[right]] == 1:
cnt += 1
while cnt > 2:
if c[fruits[left]] == 1:
cnt -= 1
c[fruits[left]] -= 1
left += 1
res = max(res, right - left + 1)
return res
不定长滑动窗口求连续子数组个数，滑动窗口结合集合视角和贡献法。
这种问题我们以集合的视角看待问题，当我们使用滑动窗口时，我们每次都在向右移动右指针。
当我们的[left, right]区间满足条件时，我们把左指针移动到刚刚不满足条件的位置，及我们把left-1, [left-1, left-2]...这个子串拼接上去后就可以合格，我们当前的区间对答案的贡献就是left， 然后res += left
第二种思路是找到合法的左端点最小值，然后分析当前区间对答案的贡献，进行累加即可。
class Solution:
def countCompleteSubarrays(self, nums: List[int]) -> int:
n = len(nums)
cnt = Counter()
m = len(set(nums))
res = left = 0
for v in nums:
cnt[v] += 1
while len(cnt) == m:
x = nums[left]
cnt[x] -= 1
if cnt[x] == 0:
del cnt[x]
left += 1
res += left
return res
class Solution:
def countSubarrays(self, nums: List[int], k: int) -> int:
n = len(nums)
mx = max(nums)
cnt = 0
res = left = 0
for v in nums:
if v == mx:
cnt += 1
while cnt >= k:
if nums[left] == mx:
cnt -= 1
left += 1
res += left
return res
class Solution:
def numberOfSubstrings(self, s: str) -> int:
n = len(s)
res = left = 0
c = Counter()
cnt = 0
for v in s:
c[v] += 1
if c[v] == 1:
cnt += 1
while cnt == 3:
c[s[left]] -= 1
if c[s[left]] == 0:
cnt -= 1
left += 1
res += left
return res
这就要那种第二个思路。
多指针滑动窗口
我们遇到的问题一般以双指针为主，需要三个及以上的指针的问题我们称之为多指针问题。
多指针滑动窗口一般的实现方法是，右端点right依旧正常每次加一，我们维护l1, l2两个指针，类似于lower_bound和upper_bound函数，每次res += l2 - l1
class Solution:
def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
n = len(nums)
l1 = l2 = res = 0
s1 = s2 = 0
for right, x in enumerate(nums):
s1 += nums[right]
s2 += nums[right]
while l1 <= right and s1 > goal:
s1 -= nums[l1]
l1 += 1
while l2 <= right and s2 >= goal:
s2 -= nums[l2]
l2 += 1
res += l2 - l1
return res
class Solution:
def numberOfSubarrays(self, nums: List[int], k: int) -> int:
n = len(nums)
l1 = l2 = res = 0
s1 = s2 = 0
for right, x in enumerate(nums):
if x & 1 == 1:
s1 += 1
s2 += 1
while l1 <= right and s1 > k:
if nums[l1] & 1 == 1:
s1 -= 1
l1 += 1
while l2 <= right and s2 >= k:
if nums[l2] & 1 == 1:
s2 -= 1
l2 += 1
res += l2 - l1
return res
标签：cnt,right,窗口,nums,int,res,模型,滑动,left From： https://www.cnblogs.com/zk6696/p/17892871.html