滑动窗口与双指针

滑动窗口

模板

def findSubArray(nums):
    N = len(nums) # 数组/字符串长度
    left, right = 0, 0 # 双指针，表示当前遍历的区间[left, right]，闭区间
    sums = 0 # 用于统计 子数组/子区间 是否有效，根据题目可能会改成求和/计数
    res = 0 # 保存最大的满足题目要求的 子数组/子串 长度
    while right < N: # 当右边的指针没有搜索到 数组/字符串 的结尾
        sums += nums[right] # 增加当前右边指针的数字/字符的求和/计数
        while sums 符合题意：# 
            res = max(res, right - left + 1) # 需要更新结果 
            sums -= nums[left] #移除值 
            left += 1   #移动左指针
        right += 1 # 移动右指针，去探索新的区间
    return res

具体讲解可以看 https://leetcode-cn.com/problems/max-consecutive-ones-iii/solution/fen-xiang-hua-dong-chuang-kou-mo-ban-mia-f76z/

注意点：滑动窗口对数据的单调性有一定的约束的，比如 和至少为k的最短子数组[862] 这道题，数组中值的累加不满足单调性，因此用滑动窗口是不行的。

总结

• 一般都是先sum数组先减去一个值，然后index再进行操作，如对于长度最小的子数组这个题目，我们发现加多了之后，不能先对left加1，而应该是先减去left的值，然后再加1。
• 左右都要移动的代码规律如下

while left < right:
    操作s[加减] 比如s是累计窗口内的和或者用来保存出现次数的字典
    条件s[判断s是否符合条件]
    条件1：
        left + 1
    条件2：
        right -1

• 右边按照1步慢慢来移动，左边自适应移动代码规律如下

for right in range(n):
    # 1. 先操作
    s = s + nums[right]【题目3 209 904】或者不操作【题目26 27 80】
    # 2. 循环左
    while condition(s)【题目3 209 904】 或者 if 【题目26 27 80】
        操作s
        保存结果ans
        left = left + 1

长度最小的子数组[209]

这是很简单的滑动窗口，没有复杂的逻辑，就是简答的滑窗，代码如下：

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        start, end = 0, 0
        s  = 0
        min_lens = float("inf")
        while end < len(nums):
            s += nums[end]
            while s >= target: # 刚好满足条件了
                if end - start + 1 < min_lens:
                    min_lens = end - start + 1
                s -= nums[start]
                start += 1
            end += 1
        if min_lens==float("inf"):
            return 0
        else:
            return min_lens

刚好满足条件了 end - start + 1

滑动窗口最大值[239]

# 1. 
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        import heapq
        q = [(-nums[i], i) for i in range(k)]
        heapq.heapify(q)
        ans = [-q[0][0]]
        for i in range(k, len(nums)):
            heapq.heappush(q, (-nums[i],i))
            while q[0][1] < i -k + 1: # 不能超过界限
                heapq.heappop(q)
            ans.append(-q[0][0])
        return ans
# 2. 
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        import heapq
        q = []
        res = []
        for i in range(len(nums)):
            if len(q) <= k - 1:
                heapq.heappush(q, (-nums[i], i))
            else:
                res.append(-q[0][0])
                while q and i - q[0][1] >= k:
                    heapq.heappop(q)
                heapq.heappush(q, (-nums[i], i))
        res.append(-q[0][0])
        return res

最好是上面的那种，push完之后立马算最小值，不然2解法中，最后还要加一个，很麻烦的

滑动窗口中位数

题目见 https://leetcode-cn.com/problems/sliding-window-median/， 题解如下：

class Solution:
    def medianSlidingWindow(self, nums, k):
        import bisect
        res = []
        res2 = []
        for i in range(len(nums)):
            if len(res) >= k:
                if k & 1:
                    res2.append(res[k // 2])
                else:
                    res2.append((res[k // 2] + res[k // 2] - 1) / 2)
                idx = bisect.bisect_left(res, nums[i - k]) # 找到位置
                res[idx:idx + 1] = [] # 清除
            idx = bisect.bisect_left(res, nums[i])
            res[idx:idx] = [nums[i]]
        return res2


su = Solution()
su.medianSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3)

最小覆盖子串[76]

题目见 https://leetcode-cn.com/problems/minimum-window-substring/， 解法如下：

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        # 定义函数
        def all_map(t, s):
            for i in t:
                if t[i] > s[i]:
                    return False
            return True

        # 定义开始和结束
        start = 0
        end = 0
        from collections import defaultdict
        t_dict = defaultdict(int)
        for i in t:  # 统计
            t_dict[i] += 1
        s_dict = defaultdict(int)
        min_len = float("inf")
        min_res = ""
        # 循环
        while end < len(s):
            s_dict[s[end]] += 1 # 注意点1，后面那道题就放在end+=1之前了
            while all_map(t_dict, s_dict): # 刚刚满足条件了
                if end - start + 1 < min_len:
                    min_len = end + 1 - start
                    min_res = s[start:end + 1]
                s_dict[s[start]] -= 1
                start += 1
            end += 1
        return min_res


su = Solution()
f = su.minWindow(s="ADOBECODEBANC", t="ABC")
print(f)

刚好满足条件了 end - start + 1

无重复字符的最长子串[3]

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 删除字典元素
        def remove_d_v(d,v):
            if v in d:
                d[v] -= 1
            if d[v]==0:
                d.pop(v)
        # 开始逻辑
        if len(s)==1:return 1
        from collections import defaultdict
        start, end = 0,0
        d = defaultdict(int)
        max_lens = 0
        while end < len(s):            
            while s[end] in d: # 刚好不满足条件了
                max_lens = max(max_lens, end - start)
                remove_d_v(d,s[start])
                start += 1
            d[s[end]] += 1 # 注意点，位置放这里
            end += 1
        return max(max_lens, end - start)

刚好不满足条件了 end - start

最长重复子串[1044]

题目见 https://leetcode-cn.com/problems/longest-duplicate-substring/ 这道题还可以用字符串哈希来做，不过比较麻烦，这里就使用常规的方法来做了

class Solution:
    def longestDupSubstring(self, s: str) -> str:
        ans = ""
        start = 0
        end = 1
        n = len(s)
        while start < n:
            while s[start:end] in s[start+1:]:
                if end - start> len(ans):
                    ans = s[start:end]
                end += 1
            start += 1
            end += 1
        return ans

大部分题解是while end < n

和大于等于 target 的最短子数组[LCR 008]

题解如下，注意一下边界的条件

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        import bisect
        prefix = [0]
        for i in nums:
            prefix.append(prefix[-1] + i)
        if prefix[-1]<target:
            return 0
        res = float("inf")
        for i in range(len(prefix)):
            index = bisect.bisect_left(prefix, prefix[i] + target)
            if index != len(prefix):           
                res = min(index - i, res)
        return 0 if res==len(prefix) else res

也可以使用滑窗解法如下：

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        if not nums:
            return 0
        
        n = len(nums)
        ans = n + 1
        start, end = 0, 0
        total = 0
        while end < n:
            total += nums[end]
            while total >= s:
                ans = min(ans, end - start + 1)
                total -= nums[start]
                start += 1
            end += 1
        
        return 0 if ans == n + 1 else ans

将 x 减到 0 的最小操作数[1658]

题目见 https://leetcode-cn.com/problems/minimum-operations-to-reduce-x-to-zero/ ，解法如下所示：

# bisect 因此nums都是正数，所以可以使用二分查找来做
class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        def get_prefix_sum(nums):
            prefix = []
            for i in nums:
                val = prefix[-1] if prefix else 0
                prefix.append(i+val)
            return prefix

        res = float("inf")
        for i in range(len(nums)):
            nums2 = nums[0:i][::-1] + nums[i:][::-1]
            prefix = get_prefix_sum(nums2)
            print(prefix)
            if x in prefix:
                res = min(res, prefix.index(x)+1)
        return -1 if res==float("inf") else res
# 滑窗
class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        diff = sum(nums) - x
        if diff < 0:
            return -1
        left = 0
        right = 0
        sm = 0
        res = -1
        while right < len(nums):
            sm += nums[right]
            while sm > diff:
                sm -= nums[left]
                left += 1
            if sm == diff:
                res = max(res,right - left + 1)
            right += 1 # 一定放这里
        return -1 if res==-1 else len(nums)-res

下标对中的最大距离[1855]

题目见 https://leetcode-cn.com/problems/maximum-distance-between-a-pair-of-values/ 按照滑动窗口模板来写的话，如下：

# 错误
class Solution:
    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:
        left = 0
        right = 0
        res = 0
        while right < len(nums2):
            while left < len(nums1) and nums1[left] > nums2[right] and left<=right:
                left += 1
            res = max(res, right-left)
            right += 1
        return res
# 正确
class Solution:
    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:
        left = 0
        right = 0
        res = 0
        while right < len(nums2):
            while left < len(nums1) and nums1[left] > nums2[right] and left<=right:
                left += 1
            if left < len(nums1):  # 这里要加一个
                res = max(res, right-left)
            right += 1
        return res

水果成篮[904]

题号 904， 位于 https://leetcode.cn/problems/fruit-into-baskets/description/
题解如下：

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        cnt = Counter()

        left = ans = 0
        for right, x in enumerate(fruits):
            cnt[x] += 1 #这里字典操作
            while len(cnt) > 2:
                cnt[fruits[left]] -= 1
                if cnt[fruits[left]] == 0:
                    cnt.pop(fruits[left])
                left += 1
            ans = max(ans, right - left + 1)
        
        return ans

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

位于 https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/ 题解看我这就好

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        s_list = [0] * 26
        p_list = [0] * 26
        for n in p:
            p_list[ord(n)-ord('a')] += 1
        left=0
        right=0
        ans = []
        while right < len(s):
            s_list[ord(s[right])-ord("a")] += 1
            if right - left >= len(p): # 发现右比左多的话，左边也动
                s_list[ord(s[left])-ord("a")] -= 1
                left = left + 1
            if s_list == p_list:
                ans.append(left)
            right = right + 1

        return ans

串联所有单词的子串 [30]

位于 https://leetcode.cn/problems/substring-with-concatenation-of-all-words/description/?envType=study-plan-v2&envId=top-interview-150 题解和上面类似

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        p = "".join(words)
        s_list = [0] * 26
        p_list = [0] * 26
        for n in p:
            p_list[ord(n) - ord('a')] += 1
        left = 0
        right = 0
        ans = []
        while right < len(s):
            s_list[ord(s[right]) - ord("a")] += 1
            if right - left >= len(p):
                s_list[ord(s[left]) - ord("a")] -= 1
                left = left + 1
            if s_list == p_list:
                d = Counter(words) # 开始一步一步查验是否存在
                for j in range(left, left + len(words) * len(words[0]), len(words[0])):
                    if s[j:j + len(words[0])] in words:
                        d[s[j:j + len(words[0])]] -= 1
                if all([i==0 for i in list(d.values())]):
                    ans.append(left)
            right = right + 1
        return ans

双指针

验证回文串[125]

位于https://leetcode.cn/problems/valid-palindrome/solutions/?envType=study-plan-v2&envId=top-interview-150

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left = 0
        right = len(s) - 1
        while left < right:
            while left < right and left < len(s) and not s[left].isalpha() and not s[left].isdigit():
                left = left + 1
            while left < right and right < len(s) and not s[right].isalpha() and not s[right].isdigit():
                right = right-1
            if s[left].lower() == s[right].lower():
                left = left + 1
                right = right - 1
            else:
                print(left, right)
                return False
        return True

判断子序列[392]

位于 https://leetcode.cn/problems/is-subsequence/description/?envType=study-plan-v2&envId=top-interview-150 感觉使用while会好一些，这样就不用判断是否index超了

# 使用while
class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        n, m = len(s), len(t)
        i = j = 0
        while i < n and j < m:
            if s[i] == t[j]:
                i += 1
            j += 1
        return i == n
# 使用for
class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        if s=="":
            return True
        p1 = 0
        for p2 in range(len(t)):
            if t[p2] == s[p1]:
                p1 = p1 + 1
                if p1 == len(s):
                    return True
        return False

移除元素[27]

位于 https://leetcode.cn/problems/remove-element/
题解如下：

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        left = 0
        for right in range(len(nums)):
            pass #这里不需要操作啥
            if nums[right] == val:
                continue
            nums[left] = nums[right]
            left = left + 1
        return left

删除有序数组中的重复项[26]

位于 https://leetcode.cn/problems/remove-duplicates-from-sorted-array/

题解如下：

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        left = 0
        for right in range(0, len(nums)):
            if nums[right] == nums[left]:
                continue
            left = left + 1
            nums[left] = nums[right]
        return left + 1

删除有序数组中的重复项 II[80]

位于 https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/
题解如下：

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        from collections import defaultdict
        left = 0
        d = defaultdict(int)
        for right in range(len(nums)):
            d[nums[right]] = d[nums[right]] + 1 # 注意点，先加1，然后再判断
            if d[nums[right]] > 2:
                continue
            nums[left] = nums[right]
            left = left + 1
        return left

轮转数组[189]

位于 https://leetcode.cn/problems/rotate-array/solutions/?envType=study-plan-v2&envId=top-interview-150

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if k==0 or len(nums)==1:
            return
        k = k % len(nums)
        num2 = nums[-k:] + nums[0:-k] # 注意
        for index, value in enumerate(num2):
            nums[index] = value

合并两个有序数组[88]

位于 https://leetcode.cn/problems/merge-sorted-array/description/?envType=study-plan-v2&envId=top-interview-150

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        p1, p2 = m - 1, n - 1
        tail = m + n - 1
        while p1 >= 0 or p2 >= 0:
            if p1 == -1:
                nums1[tail] = nums2[p2]
                p2 = p2 - 1
            elif p2 == -1:
                nums1[tail] = nums1[p1]
                p1 = p1 - 1
            elif nums1[p1] > nums2[p2]:
                nums1[tail] = nums1[p1]
                p1 = p1 - 1
            else:
                nums1[tail] = nums2[p2]
                p2 = p2 - 1
            tail = tail - 1

两数之和[1]

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        d = {}
        for i in range(len(nums)):
            d[nums[i]] = i 
        for i in range(len(nums)):
            current_value = nums[i]
            if target - current_value in d:
                if d[target - current_value]!= i:
                    return [i, d[target - current_value]]

两数之和II[167]

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        d=dict(zip(numbers,list(range(len(numbers)))))
        for i in range(len(numbers)):
            if (target-numbers[i]) in d:
                return [i+1,d[target-numbers[i]]+1]

三数之和[15]

思路:采用总结里面第2点，涉及到while i < j，代码如下：

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if not nums:
            return []
        nums.sort()
        if nums[0] == 0 and nums[-1] == 0 and len(nums) >= 3:
            return [[0, 0, 0]]
        res = []
        for i in range(len(nums) - 2):
            if nums[i] > 0:
                break
            if i >= 1 and nums[i - 1] == nums[i]:
                continue
            m, n = i + 1, len(nums) - 1
            while m < n:
                s = nums[i] + nums[m] + nums[n]
                if s < 0:
                    m = m + 1
                elif s > 0:
                    n = n - 1
                else:
                    res.append([nums[i], nums[m], nums[n]])
                    m = m + 1
                    n = n - 1
                    while m < n and nums[m] == nums[m - 1]: # 注意，不是m+1，是从后往前去你有没有重复的
                        m = m + 1
                    while m < n and nums[n] == nums[n + 1]:
                        n = n - 1
        return res

文本左右对齐[68]

位于 https://leetcode.cn/problems/text-justification/?envType=study-plan-v2&envId=top-interview-150 解法如下

class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        left = 0
        right = 0
        res = []
        while left < len(words) and right < len(words):
            str_sums = 0
            while right < len(words) and str_sums + len(words[right]) + right - left <= maxWidth: # 注意这里直接加上去
                str_sums = str_sums + len(words[right])
                right = right + 1
            res.append(words[left:right])
            left = right
        new_list = []
        for i in res[:-1]:
            diff = maxWidth - len("".join(i))
            for lens in range(diff):
                index = lens % max(1, (len(i) - 1))
                i[index] = i[index] + " "
            new_list.append("".join(i))
        new_list.append(" ".join(res[-1]) + " "*(maxWidth-len(" ".join(res[-1]))))
        return new_list

四数之和 [18]

有序数组平方和[977]

思路:采用总结里面的第2点，涉及到while i < j

训练计划I [LCR 139]

位于 https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/description/
题解如下：

class Solution:
    def trainingPlan(self, actions: List[int]) -> List[int]:
        i, j = 0, len(actions) - 1
        while i < j:
            while i < j and actions[i] & 1 == 1: i += 1
            while i < j and actions[j] & 1 == 0: j -= 1
            actions[i], actions[j] = actions[j], actions[i]
        return actions

就是上面说的第一个模版，在三数之和中也遇到了，外面一个大的while i<j里面还有两个小的while i<j然后加上一些判断条件。

盛水最多的容器 [11]

位于 https://leetcode.cn/problems/container-with-most-water/description/?envType=study-plan-v2&envId=top-interview-150
思路:采用总结里面的第2点，涉及到while i < j

题号:11

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 0
        right = len(height) - 1

        area = 0
        while left <= right:
            temp = min(height[left], height[right]) * (right - left)
            if height[left] < height[right]:
                left = left + 1
            else:
                right = right - 1
            if temp > area:
                area = temp
        return area

反转字符串中的单词[151]

位于 https://leetcode.cn/problems/reverse-words-in-a-string/description/?envType=study-plan-v2&envId=top-interview-150 代码如下

class Solution:
    def reverseWords(self, s: str) -> str:
        left = 0
        right = 0
        res = []
        while left < len(s) and right < len(s):
            while left < len(s) and s[left] == " ":
                left = left + 1
            right = left
            while right < len(s) and s[right] != " ":
                right = right + 1
            res.append(s[left:right])
            left = right
        return " ".join(res[::-1]).strip()

验证回文串[125]

位于 https://leetcode.cn/problems/valid-palindrome/description/?envType=study-plan-v2&envId=top-interview-150 代码如下

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left = 0
        right = len(s) - 1
        while left < right:
            while left < right and left < len(s) and not s[left].isalpha() and not s[left].isdigit(): #注意点1
                left = left + 1
            while left < right and right < len(s) and not s[right].isalpha() and not s[right].isdigit():
                right = right-1
            if s[left].lower() == s[right].lower():
                left = left + 1
                right = right - 1
            else:
                print(left, right)
                return False
        return True

判断子序列 [392]

位于 https://leetcode.cn/problems/is-subsequence/description/?envType=study-plan-v2&envId=top-interview-150 题解如下

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        if s=="":
            return True
        p1 = 0
        for p2 in range(len(t)):
            if t[p2] == s[p1]:
                p1 = p1 + 1
                if p1 == len(s):
                    return True
        return False