C語言字符串中的滑動窗口算法

滑動窗口算法是一種在字符串或數(shù)組上操作的技巧，它可以在不重復計算的情況下，高效地遍歷數(shù)據(jù)結(jié)構(gòu)

1. 定義兩個指針，left 和 right，分別表示窗口的左邊界和右邊界。
2. 初始化窗口大小，例如設置 left = 0, right = 0。
3. 使用一個循環(huán)來移動 right 指針，擴大窗口。在每次迭代中，檢查當前窗口是否滿足條件（例如，最大子數(shù)組和、最長子字符串等）。
4. 如果當前窗口滿足條件，嘗試通過移動 left 指針來縮小窗口，同時更新窗口內(nèi)的信息（例如，子數(shù)組和、子字符串長度等）。
5. 當窗口無法繼續(xù)滿足條件時，停止循環(huán)。

以下是一個 C 語言實現(xiàn)的滑動窗口算法示例，用于查找字符串中最長的連續(xù)子串，該子串中的所有字符都是唯一的：

#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}; // 用于存儲字符出現(xiàn)的位置

    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 的數(shù)組來存儲每個字符最后出現(xiàn)的位置。當我們遇到一個重復字符時，我們將左邊界移動到該字符上次出現(xiàn)的位置之后。這樣，我們可以確保窗口內(nèi)的所有字符都是唯一的。在每次更新窗口時，我們還會檢查當前窗口的長度是否大于之前找到的最長子串，并相應地更新結(jié)果。