1.滑动窗口
补:滑动窗口问题可枚举右端点,滑动左端点。
模板
# 窗口的左右边界
class solution:
def Solution():
l,r=0,0 # 窗口左右边界
ans=0
while r<n:
# Other Code
while 判断条件 and l<=r:
# Other Code
l+=1
r+=1
return ans
例题一
力扣713:
class Solution:
def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
ans, left, cur = 0, 0, 1
for right, num in enumerate(nums):
cur *= num
print(cur)
# 当前到右指针的连乘太大,需要一直挪动左指针直到小于k
while left <= right and cur >= k:
cur //= nums[left]
left += 1
# 在left到right之间的i, nums[i:right+1]的连乘都满足小于k
# 知道这个很重要,也是本题的重点
ans += right - left + 1
return ans
例题2
力扣3
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
# 哈希集合,记录每个字符是否出现过,这题重点就是使用集合
occ = set()
n = len(s)
# 右指针,初始值为 -1,相当于我们在字符串的左边界的左侧,还没有开始移动
rk, ans = -1, 0
for i in range(n):
if i != 0:
# 左指针向右移动一格,移除一个字符
occ.remove(s[i - 1])
while rk + 1 < n and s[rk + 1] not in occ:
# 不断地移动右指针
occ.add(s[rk + 1])
rk += 1
# 第 i 到 rk 个字符是一个极长的无重复字符子串
ans = max(ans, rk - i + 1)
return ans
Comments NOTHING