四.滑动窗口

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

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        res = 0
        visited = list()
        for i in range(len(s)):
            # 左移窗口
            while s[i] in visited: visited.pop(0)
            # 右移窗口
            visited.append(s[i])
            res = max(res, len(visited))
        return res

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

class Solution:
    def isSame(self, s: list, p: list) -> bool:
        s.sort(); p.sort()
        return s == p
    def findAnagrams(self, s: str, p: str) -> List[int]:
        res = list()
        n = len(p)
        ss = list(s); pp = list(p)
        for i in range(0, len(s)-n+1):
            if self.isSame(ss[i:i+n], pp): res.append(i)
        return res

剑指 Offer II 014. 字符串中的变位词

class Solution:
    def isSame(self, s: list, p: list) -> bool:
        s.sort(); p.sort()
        return s == p
    def checkInclusion(self, s1: str, s2: str) -> bool:
        res = list()
        n = len(s1)
        ss = list(s2); pp = list(s1)
        for i in range(0, len(s2)-n+1):
            if self.isSame(ss[i:i+n], pp): return True
        return False

剑指 Offer II 009. 乘积小于 K 的子数组

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        total = 1; res = 0
        left = 0       
        for right, num in enumerate(nums):
            total *= nums[right]
            while left <= right and total >= k:
                total //= nums[left]
                left += 1
            res += right-left+1
        return res

剑指 Offer II 008. 和大于等于 target 的最短子数组

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        left = res = total = 0
        if sum(nums) < target:
            return 0
        else:
            res = sum(nums)
        for right, num in enumerate(nums):
            total += num
            while total >= target:
                res = min(res, right-left+1)
                total -= nums[left]
                left += 1               
        return res