滑动窗口技术在数据结构与算法中的应用

滑动窗口技术是一种强大的方法，常用于解决涉及子数组或子字符串的问题。该方法通过维护一个窗口，在数组或字符串上滑动以处理一部分元素。窗口的大小可以是固定的或可变的，具体取决于问题的要求。

一. 固定大小窗口

1.1 找到大小为 k 的子数组的最大和

以下是一个 C# 代码示例，演示如何使用滑动窗口技术找到大小为 k 的子数组的最大和。

public static int MaxSumSubarray(int[] arr, int k)
{
    int n = arr.Length; // 获取数组的长度

    int maxSum = 0; // 初始化最大和为0
    for (int i = 0; i < k; i++) // 计算前k个元素的和
    {
        maxSum += arr[i]; // 累加前k个元素
    }
    
    int windowSum = maxSum; // 将初始窗口和赋值给windowSum
    for (int i = k; i < arr.Length; i++) // 从k-th元素开始滑动窗口
    {
        windowSum += arr[i] - arr[i - k]; // 更新窗口和：加入新元素，移除旧元素
        maxSum = Math.Max(windowSum, maxSum); // 更新最大和
    }
    return maxSum; // 返回最大子数组和
}

1.2 使用示例

int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; // 示例数组
int k = 3; // 子数组的大小
Console.WriteLine("最大和为大小为 " + k + " 的子数组是 " + MaxSumSubarray(arr, k)); // 输出最大和

1.3 输出结果

最大和为大小为 3 的子数组是 27

1.4 时间复杂度

时间复杂度为 O(n)，其中 n 是数组的长度。

二. 可变大小滑动窗口

2.1 找到最长的无重复字符子字符串

以下是一个 C# 代码示例，演示如何使用滑动窗口技术找到最长的无重复字符的子字符串。

public static int LengthOfLongestSubstring(string s)
{
    int n = s.Length; // 获取字符串的长度
    int maxLength = 0; // 初始化最长子字符串长度为0
    int start = 0; // 当前窗口的起始索引初始化为0
    int end = 0; // 当前窗口的结束索引初始化为0
    Dictionary<char, int> dict = new Dictionary<char, int>(); // 字典存储每个字符的最后索引

    for (end = 0; end < n; end++) // 遍历字符串
    {
        char currentChar = s[end]; // 当前结束索引处的字符
        if (dict.ContainsKey(currentChar) && dict[currentChar] >= start) // 检查是否出现重复字符
        {
            start = dict[currentChar] + 1; // 移动起始索引到重复字符的下一个位置
        }
        dict[currentChar] = end; // 更新字符的最后索引
        maxLength = Math.Max(maxLength, end - start + 1); // 更新最大长度
    }
    return maxLength; // 返回最长无重复字符子字符串的长度
}

2.2 使用示例

string s = "abcabcbb"; // 示例字符串
Console.WriteLine("最长无重复字符子字符串的长度为 " + LengthOfLongestSubstring(s)); // 输出长度

2.3 输出结果

最长无重复字符子字符串的长度为 3

2.4 时间复杂度

时间复杂度为 O(n)，其中 n 是字符串的长度。

三. 结论

滑动窗口技术提供了一种高效处理子数组或子字符串问题的方法。通过使用固定大小或可变大小的窗口，我们能够以线性时间复杂度解决许多常见问题。这种技术不仅简化了代码，还提高了程序的执行效率。在实际应用中，滑动窗口技术被广泛应用于字符串处理、数组分析等领域。