Leetcode 滑动窗口题目总结

**滑动窗口题目总结**

滑动窗口是一种常见的算法思想，用于解决涉及窗口移动的问题。它通常涉及到维护一个固定大小的窗口，并在满足某些条件时向左或右移动这个窗口。

###什么是滑动窗口？

滑动窗口是一种抽象概念，它代表了一个固定大小的区域，用于存储和操作数据。在滑动窗口中，我们通常需要维护两个指针：一个左边界（左端点）和一个右边界（右端点）。这些指针决定了窗口的大小和位置。

### 滑动窗口的应用场景滑动窗口有许多应用场景，包括：

* **最大/最小子数组问题**：找出给定数组中连续子数组的最大/最小值。
* **最长公共子序列问题**：找到两个字符串的最长公共子序列。
* **滑动平均问题**：计算给定数据集的滑动平均值。
* **窗口和计数问题**：在给定的数组中找出满足某些条件的连续子数组的数量。

### 滑动窗口算法步骤1. **初始化窗口**: 初始化左边界（左端点）和右边界（右端点），以及一个变量来存储当前窗口的大小。
2. **移动窗口**: 根据给定的条件，向左或向右移动窗口。例如，如果我们正在寻找最大子数组，那么当右边界超过当前最大值时，我们需要向左移动窗口。
3. **更新结果**: 在每次移动窗口后，更新结果变量以包含当前窗口的信息。

### 滑动窗口示例代码#### 示例1：最大子数组问题

def maxSubArray(nums):
 if not nums:
 return0 # 初始化窗口大小为1 window_size =1 # 初始化结果变量 result = float('-inf')
 while window_size <= len(nums):
 # 初始化左边界和右边界 left =0 right = window_size # 移动窗口并更新结果 while right < len(nums):
 # 计算当前窗口的值 current_sum = sum(nums[left:right])
 # 更新结果变量 result = max(result, current_sum)
 # 向右移动窗口 left +=1 right +=1 # 向左移动窗口大小 window_size +=1 return result# 测试示例nums = [-2, -3,4, -1, -2,1,5, -3]
print(maxSubArray(nums)) # 输出:7

def longestCommonSubsequence(text1, text2):
 m = len(text1)
 n = len(text2)
 # 初始化结果变量 result = ''
 # 初始化左边界和右边界 left =0 right =0 while left < m and right < n:
 # 如果当前字符匹配，则更新结果变量并向右移动窗口 if text1[left] == text2[right]:
 result += text1[left]
 left +=1 right +=1 # 否则，向左移动窗口 elif left < m -1 and text1[left +1] == text2[right]:
 left +=1 else:
 right +=1 return result# 测试示例text1 = "abcde"
text2 = "ace"
print(longestCommonSubsequence(text1, text2)) # 输出: "ace"

def movingAverage(nums, k):
 m = len(nums)
 # 初始化结果变量 result = []
 # 初始化左边界和右边界 left =0 while left < m:
 # 计算当前窗口的平均值并添加到结果变量中 current_sum = sum(nums[left:left + k])
 result.append(current_sum / k)
 # 向右移动窗口 left +=1 return result# 测试示例nums = [1,2,3,4,5]
k =2print(movingAverage(nums, k)) # 输出: [1.5,2.5,3.5,4.5]

def countSubarrays(nums):
 m = len(nums)
 # 初始化结果变量 result =0 # 初始化左边界和右边界 left =0 while left < m:
 # 计算当前窗口的值并更新结果变量 current_sum = sum(nums[left:m])
 # 如果当前窗口的值为偶数，则增加结果变量 if current_sum %2 ==0:
 result +=1 # 向右移动窗口 left +=1 return result# 测试示例nums = [1,2,3,4,5]
print(countSubarrays(nums)) # 输出:6