python 窗口滑动算法
时间: 2023-11-07 22:08:15 浏览: 42
窗口滑动算法是一种常见的算法思想,它在处理连续的子序列问题时非常有效。下面是一个Python实现的窗口滑动算法示例:
```python
def sliding_window(nums, k):
if not nums:
return []
n = len(nums)
if k == n:
return [sum(nums)]
res = []
window_sum = sum(nums[:k])
res.append(window_sum)
for i in range(k, n):
window_sum += nums[i] - nums[i-k]
res.append(window_sum)
return res
```
该函数的参数包括一个整数列表nums和一个窗口大小k,函数返回一个由所有窗口的和组成的列表。算法的核心是使用双指针来维护一个窗口,然后在每个窗口上计算和。具体来说,我们首先计算最初的窗口和,然后在每个窗口上向右移动时,我们将窗口的左侧指针向右移动一个位置,将右侧指针向右移动一个位置,然后重新计算窗口和。重复此过程,直到我们遍历完整个列表。
相关问题
python 滑动窗口算法
滑动窗口算法是一种常用的算法,可以用来解决一些字符串和数组相关的问题。其基本思想是维护一个窗口,通过移动窗口来寻找符合条件的子串或子数组。
具体来说,滑动窗口算法通常包含以下几个步骤:
1. 初始化窗口的起始位置和结束位置;
2. 移动窗口的结束位置,直到找到符合条件的子串或子数组;
3. 移动窗口的起始位置,缩小窗口范围,直到不符合条件为止;
4. 重复步骤2和3,直到遍历完整个字符串或数组。
下面是一个示例代码,用来寻找一个数组中长度为k的连续子数组的最大值:
```python
def max_subarray(nums, k):
n = len(nums)
if n < k:
return None
max_sum = sum(nums[:k])
window_sum = max_sum
for i in range(k, n):
window_sum += nums[i] - nums[i-k]
max_sum = max(max_sum, window_sum)
return max_sum
```
在这个代码中,我们维护了一个长度为k的窗口,每次移动窗口时,只需要加上新的元素,减去旧的元素即可。同时,我们用一个变量max_sum来记录当前找到的最大值。
python滑动窗口算法
Python的滑动窗口算法可以用来解决很多实际问题,例如字符串匹配、子数组求和等问题。下面是一个示例代码:
```python
def sliding_window(nums, k):
"""
滑动窗口算法
nums: 数组
k: 窗口大小
"""
n = len(nums)
if n < k:
return []
# 初始化窗口
window = []
for i in range(k):
window.append(nums[i])
res = [sum(window)]
# 滑动窗口
for i in range(k, n):
# 移除窗口最左侧的元素
window.pop(0)
# 添加新的元素
window.append(nums[i])
res.append(sum(window))
return res
```
这个函数接收两个参数,一个是数组nums,另一个是窗口大小k。函数首先检查数组长度是否小于k,如果是,则返回空数组。然后初始化一个大小为k的窗口,将窗口内的元素求和作为第一个结果。接下来,从第k个元素开始遍历数组,每次移除窗口最左侧的元素,添加新的元素,再求和并添加到结果数组中。最后返回结果数组。
这里是一个示例使用:
```python
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
res = sliding_window(nums, k)
print(res) # [3, -1, 1, 7, 11, 16]
```
这个示例中,数组nums为[1, 3, -1, -3, 5, 3, 6, 7],窗口大小为3。函数的输出结果为[3, -1, 1, 7, 11, 16],表示每个窗口内的元素和。