基础算法：滑动窗口

能使用滑动窗口的题，基本都需要数字为正整数，这样才能保证滑入一个数字总和是增加的(单调性)

一、209. 长度最小的子数组

• 思路：

  已每个位置为右端点，依次加大左端点，最短不满足 sum(num[left,right])

• 代码：

  class Solution:
      def minSubArrayLen(self, target: int, nums: List[int]) -> int:
          n = len(nums)
          ans = n + 1  # 也可以写 inf
          s = left = 0
          for right, x in enumerate(nums):  # 枚举子数组右端点
              s += x
              while s >= target:  # 满足要求
                  ans = min(ans, right - left + 1)
                  s -= nums[left]
                  left += 1  # 左端点右移
          return ans if ans  int:
          if k = k:  # 不满足要求
                  prod //= nums[left]
                  left += 1
              ans += right - left + 1
          return ans
  

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

  

  • 思路1：

    还是一样，站在每个右端点，如果当前串内有重复的字符。依次移除左端点的

  • 代码：

    class Solution:
        def lengthOfLongestSubstring(self, s: str) -> int:
            ans = left = 0
            cnt = defaultdict(int)  # 维护从下标 left 到下标 right 的字符及其出现次数
            for right, c in enumerate(s):
                cnt[c] += 1
                while cnt[c] > 1:  # 窗口内有重复字母
                    cnt[s[left]] -= 1  # 移除窗口左端点字母
                    left += 1  # 缩小窗口
                ans = max(ans, right - left + 1)  # 更新窗口长度最大值
            return ans
    

    • 思路2：

      依次遍历s，不是重复字符直接加入并计算长度，遇到重复字符，那么当前字符要退出到上一个重复位置。列表可采用 list.index(i)，找到i字符在列表中的位置。

    • 代码：

      class Solution:
          def lengthOfLongestSubstring(self, s: str) -> int:
              tmp_s = []
              max_len = 0
              for i in s:
                  if i not in tmp_s:
                      tmp_s.append(i)
                      max_len = max(max_len, len(tmp_s))
                  else:
                      index = tmp_s.index(i)               
                      tmp_s = tmp_s[index+1:]
                      tmp_s.append(i)
              return max_len