class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
cnt = defaultdict(int)
left = res = 0
for i, e in enumerate(s):
cnt[e] += 1
while cnt[e] > 1:
cnt[s[left]] -= 1
left += 1
res = max(res, i - left + 1)
return res
class Solution:
def maximumLengthSubstring(self, s: str) -> int:
cnt = defaultdict(int)
left = ans = 0
for right, e in enumerate(s):
cnt[e] += 1
while cnt[e] > 2:
cnt[s[left]] -= 1
left += 1
ans = max(ans, right - left + 1)
return ans
class Solution:
def longestSubarray(self, nums: List[int]) -> int:
cnt_0 = 0
left = ans = 0
for right, e in enumerate(nums):
if e == 0:
cnt_0 += 1
while cnt_0 > 1:
if nums[left] == 0:
cnt_0 -= 1
left += 1
ans = max(ans, right - left)
return ans
class Solution:
def minRemoval(self, nums: List[int], k: int) -> int:
nums.sort()
left = ans = 0
for i, e in enumerate(nums):
while nums[left] * k < e:
left += 1
ans = max(ans, i - left + 1)
return len(nums) - ans
class Solution:
def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
cnt = 0
ans = left = 0
for i in range(len(s)):
cnt += abs(ord(s[i]) - ord(t[i]))
while cnt > maxCost:
cnt -= abs(ord(s[left]) - ord(t[left]))
left += 1
ans = max(ans, i - left + 1)
return ans
class Solution:
def totalFruit(self, fruits: List[int]) -> int:
cnt = defaultdict(int)
left = ans = 0
for i, e in enumerate(fruits):
cnt[e] += 1
while len(cnt) > 2:
out = fruits[left]
cnt[out] -= 1
if cnt[out] == 0:
del cnt[out]
left += 1
ans = max(ans, i - left + 1)
return ans
class Solution:
def maximumUniqueSubarray(self, nums: List[int]) -> int:
cnt = defaultdict(int)
left = ans = tmp = 0
for i, e in enumerate(nums):
cnt[e] += 1
tmp += e
while cnt[e] > 1:
out = nums[left]
cnt[out] -= 1
left += 1
tmp -= out
ans = max(ans, tmp)
return ans
class Solution:
def fun(self, nums, goal):
s = cnt = left = 0
for i, e in enumerate(nums):
s += e
while s >= goal and left <= i:
out = nums[left]
s -= out
left += 1
cnt += left
return cnt
def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
upper = self.fun(nums, goal)
lower = self.fun(nums, goal + 1)
return upper - lower
答案就是元素和≥k的子数组个数，减去元素和≥k + 1的子数组个数。
class Solution:
def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
if k <= 1:
return 0
left = cnt = 0
tmp = 1
for i, e in enumerate(nums):
tmp *= e
while tmp >= k:
tmp //= nums[left]
left += 1
cnt += i - left + 1
return cnt
这个注意的是left和right中间的都算
class Solution:
def numberOfSubstrings(self, s: str) -> int:
cnt = defaultdict(int)
left = ans = 0
for i, e in enumerate(s):
cnt[e] += 1
while len(cnt) == 3:
out = s[left]
cnt[out] -= 1
left += 1
if cnt[out] == 0:
del cnt[out]
ans += left
return ans
class Solution:
def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:
cnt = defaultdict(int)
ans = left = 0
for i, e in enumerate(answerKey):
cnt[e] += 1
while cnt['T'] > k and cnt['F'] > k:
out = answerKey[left]
cnt[out] -= 1
left += 1
ans = max(ans, i - left + 1)
return ans如果 T 和 F 的出现次数都超过 k，就移动左端点 left，直到 T 和 F 的出现次数至少有一个 ≤k