C语言字符串中的滑动窗口算法

滑动窗口算法是一种在字符串或数组上操作的技巧，它可以在不重复计算的情况下，高效地遍历数据结构

1. 定义两个指针，left 和 right，分别表示窗口的左边界和右边界。
2. 初始化窗口大小，例如设置 left = 0, right = 0。
3. 使用一个循环来移动 right 指针，扩大窗口。在每次迭代中，检查当前窗口是否满足条件（例如，最大子数组和、最长子字符串等）。
4. 如果当前窗口满足条件，尝试通过移动 left 指针来缩小窗口，同时更新窗口内的信息（例如，子数组和、子字符串长度等）。
5. 当窗口无法继续满足条件时，停止循环。

以下是一个 C 语言实现的滑动窗口算法示例，用于查找字符串中最长的连续子串，该子串中的所有字符都是唯一的：

#include<stdio.h>
#include<string.h>

void findLongestSubstring(char *str) {
    int left = 0, right = 0;
    int maxLength = 0;
    int start = 0;
    int charIndex[256] = {0}; // 用于存储字符出现的位置

    while (str[right] != '\0') {
        if (charIndex[str[right]] == 0 || charIndex[str[right]]< left) {
            charIndex[str[right]] = right + 1;
            right++;
        } else {
            if (right - left > maxLength) {
                maxLength = right - left;
                start = left;
            }
            left = charIndex[str[right]];
        }
    }

    if (right - left > maxLength) {
        maxLength = right - left;
        start = left;
    }

    printf("Longest substring without repeating characters: ");
    for (int i = start; i< start + maxLength; i++) {
        printf("%c", str[i]);
    }
    printf("\n");
}

int main() {
    char str[] = "abcabcbb";
    findLongestSubstring(str);
    return 0;
}

这个示例中，我们使用一个名为 charIndex 的数组来存储每个字符最后出现的位置。当我们遇到一个重复字符时，我们将左边界移动到该字符上次出现的位置之后。这样，我们可以确保窗口内的所有字符都是唯一的。在每次更新窗口时，我们还会检查当前窗口的长度是否大于之前找到的最长子串，并相应地更新结果。