数组中的灵活思想之一——滑动窗口（附LeetCode实例）

滑动数组的基本思想

在编程中，处理数组（或列表）时，滑动数组是一种非常有用的技术。它通常用于解决需要在连续的子数组或子列表上执行操作的问题。这种技术的关键思想是通过在数组上“滑动”一个固定大小的窗口来解决问题。让我们深入了解滑动数组的原理，并通过相应的示例演示其应用。

滑动数组的基本原理

滑动数组的核心概念是使用两个指针（或索引）来定义一个窗口，并在数组上移动该窗口以执行特定操作。这样的窗口通常是固定大小的，而滑动的步长取决于问题的要求。这种方法的优势在于它能够在线性时间内解决问题，而不需要嵌套的循环。

通常应用场景

1. 寻找子数组中总和的最大/最小值

假设我们有一个包含整数的数组，我们想要找到长度为 k 的子数组的最大值。使用滑动数组的方法，我们可以轻松地在线性时间内解决这个问题。同理，我们找特定条件的子数组也是如此。

def max_in_subarray(nums, k):
    max_sum = float('-inf')
    current_sum = 0

    for i in range(len(nums)):
        current_sum += nums[i]

        if i >= k - 1:
            max_sum = max(max_sum, current_sum)
            current_sum -= nums[i - (k - 1)]

    return max_sum

nums = [1, 2, 3, 1, 4, 2, 3]
print(max_in_subarray(nums, k=2))  # 输出6，对应大小为2的子数组为[4,2]
print(max_in_subarray(nums, k=3))  # 输出9，对应大小为3的子数组为[4,2,3]

2. 寻找子数组中的平均值

类似地，我们可以使用滑动数组来找到数组中长度为 k 的子数组的平均值。

def average_in_subarray(nums, k):
    averages = []

    current_sum = sum(nums[:k])
    averages.append(current_sum / k)

    for i in range(k, len(nums)):
        current_sum += nums[i] - nums[i - k]
        averages.append(current_sum / k)

    return averages

nums = [1, 2, 3, 1, 4, 2, 3]
print(average_in_subarray(nums, k=6))  
# 输出[2.1666666666666665, 2.5],对应计算的子数组为[1, 2, 3, 1, 4, 2],[2, 3, 1, 4, 2, 3]
print(average_in_subarray(nums, k=4))  
# 输出[1.75, 2.5, 2.5, 2.5],对应计算的子数组为[1, 2, 3, 1],[2, 3, 1, 4],[3, 1, 4, 2],[1, 4, 2, 3]

【LeetCode实例：219. 存在重复元素 II】

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

示例 1：

输入： nums = [1,2,3,1], k = 3
输出： true

示例 2：

输入： nums = [1,0,1,1], k = 1
输出： true

示例 3：

输入： nums = [1,2,3,1,2,3], k = 2
输出： false

  提示：

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• 0 <= k <= 10^5

python题解如下：

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        s = set()
        for i in range(n):
            if i > k:         # 子数组超过k的范围则将子数组（集合s）最前面的元素去掉
                s.remove(nums[i-k-1])
            if nums[i] in s:  # 如果子数组中存在相同的元素则返回True
                return True
            s.add(nums[i])    # 下标小于等于k时，即起始滑窗长度还不足k+1，直接往滑窗将元素nums[i]加入到集合s中
        return False

总结

滑动数组是一种灵活而高效的方法，适用于解决许多与连续子数组有关的问题。通过定义适当大小的窗口，并在数组上移动该窗口，我们可以在线性时间内解决许多复杂的问题。这种技术在处理大规模数据时尤为有用，因为它避免了嵌套循环，提高了算法的效率。在编写代码时，考虑使用滑动数组作为解决问题的工具，以提高代码的可读性和性能。

如果有兴趣的小伙伴也可以去试下209. 长度最小的子数组，此题也是滑动窗口思想解题，本人也是正在学习中，如有错误的地方欢迎大家指正，同时也希望这篇文章能给大家带来帮助。