leetcode分类刷题：滑动窗口（二、重复元素类型）

1、连续子数组、连续子串问题通常需要滑动窗口来求解，本篇文章对应的“二、重复元素类型”在此基础上对连续子数组、连续子串中重复元素个数、种类进行考察，此时，需要使用和维护哈希表进行左右指针的移动，因此这类题目对应的解法为：滑动窗口+哈希表
2、这类问题最关键的还是思考清楚左右指针如何更新：右指针遍历数组，左指针在哈希表满足一定条件时更新

904. 水果成篮

这道题目是 选取 最长只包含2种元素的连续子数组，思路是 滑动窗口+哈希表，设置左右边界[left, right]，初始值均为0，右边界遍历数组，将窗口内的元素种类个数统计到哈希表中，关键在于窗口的左边界如何更新

from typing import List
import collections'''
904. 水果成篮
题目描述：你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。
示例 1:输入：fruits = [1,2,3,2,2]输出：4解释：可以采摘 [2,3,2,2] 这四棵树。
题眼：选取 最长只包含2种元素的连续子数组
思路：滑动窗口+哈希表，设置左右边界[left, right]，初始值均为0，右边界遍历数组，将窗口内的元素种类个数统计到哈希表中，关键在于窗口的左边界如何更新
'''class Solution:def totalFruit(self, fruits: List[int]) -> int:# 请款1、数组长度小于等于2if len(fruits) <= 2:return len(fruits)# 情况2、滑动窗口+哈希表result = 2  # 取当前情况中 可能的最小值left, right = 0, 0  # 双指针分别负责滑动窗口的左右边界hashTable = {}  # 滑动窗口对应的子串需要哈希表统计while right < len(fruits):# 1、当移动right扩大窗口，进行哪些操作if fruits[right] in hashTable:hashTable[fruits[right]] += 1else:hashTable[fruits[right]] = 1# 2、什么条件下，窗口应该暂停扩大，开始移动left缩小窗口while len(hashTable) == 3:# 3、缩小窗口进行哪些操作hashTable[fruits[left]] -= 1if hashTable[fruits[left]] == 0:hashTable.pop(fruits[left])left += 1# 4、更新结果result = max(result, right - left + 1)  # 滑窗[left, right]是左闭右闭区间，子数组长度==元素个数right += 1return resultif __name__ == '__main__':obj = Solution()while True:try:in_line = input().strip().split('=')[1].strip()[1: -1]nums = []if in_line != '':for n in in_line.split(','):nums.append(int(n))# print(nums)print(obj.totalFruit(nums))except EOFError:break

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

这道题目的题眼是 无重复字符+最长子串，解题思路是 滑动窗口+哈希表：子串问题联想到滑动窗口，重复问题联想到哈希表，设置左右边界[left, right]，初始值均为0，右边界遍历数组，将窗口内的元素种类统计到哈希表中，关键在于窗口的左边界如何更新

'''
3. 无重复字符的最长子串
题目描述：给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度
示例 1:输入: s = "abcabcbb"输出: 3解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
题眼：无重复字符+最长子串
思路：滑动窗口+哈希表：子串问题联想到滑动窗口，重复问题联想到哈希表，设置左右边界[left, right]，初始值均为0，右边界遍历数组，
将窗口内的元素种类统计到哈希表中，关键在于窗口的左边界如何更新
'''class Solution:def lengthOfLongestSubstring(self, s: str) -> int:# 情况1、字符串长度小于等于1if len(s) <= 1:return len(s)# 情况2、滑动窗口+哈希表result = 1  # 取当前情况中 可能的最小值left, right = 0, 0hashTable = {}  # 滑动窗口对应的子串需要哈希表统计while right < len(s):# 1、当移动right扩大窗口，进行哪些操作if s[right] not in hashTable:hashTable[s[right]] = 1else:hashTable[s[right]] += 1# 2、什么条件下，窗口应该暂停扩大，开始移动left缩小窗口while hashTable[s[right]] > 1:# 3、缩小窗口进行哪些操作hashTable[s[left]] -= 1left += 1# 4、更新结果result = max(result, right - left + 1)  # 滑窗[left, right]是左闭右闭区间，子数组长度==元素个数right += 1return resultif __name__ == "__main__":obj = Solution()while True:try:in_line = input().strip().split('=')[1].strip()[1: -1]s = ""if in_line != "":s = in_lineprint(obj.lengthOfLongestSubstring(s))except EOFError:break