双指针与滑动窗口：从入门到实战

大家好，欢迎来到《C语言算法专题精讲》。今天我们来聊聊双指针和滑动窗口。这两个技巧，说白了就是「用两个指针来优化遍历过程」。我刚开始学的时候也觉得没什么，直到在项目中处理一个上百万条数据的日志文件，才发现暴力解法根本跑不动。嗯，从那以后，我对这两个技巧就格外上心了。

一、双指针技巧：快慢指针与左右指针

双指针的核心思想很简单：用两个指针协同工作，代替单指针的暴力遍历。根据指针的移动方式，我习惯把它们分成两类。

1. 快慢指针

快慢指针，顾名思义，一个走得快，一个走得慢。最常见的场景就是「检测链表是否有环」。快指针每次走两步，慢指针每次走一步。如果有环，它们一定会相遇。

我在项目中遇到过一个问题：需要从一个有序数组中删除重复项。用快慢指针，一次遍历就能搞定。

int removeDuplicates(int* nums, int numsSize) {
    if (numsSize == 0) return 0;
    int slow = 0;  // 慢指针指向「已处理区域的最后一个」
    for (int fast = 1; fast < numsSize; fast++) {
        if (nums[fast] != nums[slow]) {
            slow++;
            nums[slow] = nums[fast];
        }
    }
    return slow + 1;
}

你看，快指针负责「探索」，慢指针负责「确认」。这就是快慢指针的精髓。

我的小技巧： 写快慢指针时，先想清楚「慢指针的含义是什么」。是「已处理区域的边界」？还是「待处理区域的起点」？想清楚再动笔。

2. 左右指针

左右指针，通常用在有序数组或字符串中。左指针从左边开始，右指针从右边开始，向中间靠拢。

最经典的例子就是「两数之和 II - 输入有序数组」。给定一个升序数组和一个目标值，找到两个数之和等于目标值。

int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {
    int left = 0, right = numbersSize - 1;
    while (left < right) {
        int sum = numbers[left] + numbers[right];
        if (sum == target) {
            int* result = (int*)malloc(2 * sizeof(int));
            result[0] = left + 1;
            result[1] = right + 1;
            *returnSize = 2;
            return result;
        } else if (sum < target) {
            left++;  // 和太小，左指针右移
        } else {
            right--; // 和太大，右指针左移
        }
    }
    *returnSize = 0;
    return NULL;
}

为什么会这样？因为数组是有序的。左指针右移，和变大；右指针左移，和变小。你想想看，这比暴力枚举快了多少倍？

我曾经踩过的坑： 有一次我忘了数组是有序的，直接用了左右指针。结果左指针右移时，和反而变小了……嗯，从那以后我每次用左右指针前，都会先确认数据是否有序。

二、滑动窗口框架

滑动窗口，其实是双指针的一种特殊形式。两个指针维护一个「窗口」，窗口在数组或字符串上滑动。我个人觉得，滑动窗口最核心的是「什么时候扩大窗口，什么时候缩小窗口」。

我总结了一个通用框架，你可以直接套用：

/* 滑动窗口算法框架 */
void slidingWindow(char* s) {
    int left = 0, right = 0;
    // 用于记录窗口内的情况，比如字符出现次数
    int window[256] = {0};  
    
    while (right < strlen(s)) {
        // 扩大窗口：将 right 指向的字符加入窗口
        char c = s[right];
        window[c]++;
        right++;
        
        // 判断是否需要缩小窗口
        while (/* 窗口需要缩小的条件 */) {
            // 缩小窗口：将 left 指向的字符移出窗口
            char d = s[left];
            window[d]--;
            left++;
        }
        
        // 此时窗口满足条件，可以更新答案
    }
}

这个框架，说白了就是「先扩大，再缩小，中间更新答案」。我建议你把这个框架背下来，遇到滑动窗口的题，直接往上套。

三、最长无重复子串

这是滑动窗口的经典题目。给定一个字符串，找出其中不含有重复字符的最长子串的长度。

举个例子："abcabcbb"，最长无重复子串是 "abc"，长度为 3。

用滑动窗口怎么解？

int lengthOfLongestSubstring(char* s) {
    int window[256] = {0};  // 记录字符出现次数
    int left = 0, right = 0;
    int maxLen = 0;
    int len = strlen(s);
    
    while (right < len) {
        // 扩大窗口
        char c = s[right];
        window[c]++;
        right++;
        
        // 如果出现重复字符，缩小窗口
        while (window[c] > 1) {
            char d = s[left];
            window[d]--;
            left++;
        }
        
        // 更新最大长度
        if (right - left > maxLen) {
            maxLen = right - left;
        }
    }
    
    return maxLen;
}

你想想看，这个算法的时间复杂度是 O(n)，空间复杂度是 O(1)（因为 window 数组大小固定为 256）。比暴力解法的 O(n²) 不知道高到哪里去了。

核心要点： 当窗口内出现重复字符时，不断缩小左边界，直到重复字符被移出窗口。这就是「先扩大，再缩小」的典型应用。

四、最小覆盖子串

这道题比上一道难一些。给定一个字符串 S 和一个字符串 T，在 S 中找出包含 T 所有字符的最短子串。

举个例子：S = "ADOBECODEBANC"，T = "ABC"，最短覆盖子串是 "BANC"。

这道题我当年面试时遇到过，当时没写出来……嗯，后来我认真总结了一下，其实还是滑动窗口框架。

char* minWindow(char* s, char* t) {
    int need[256] = {0};  // 记录 T 中每个字符需要的次数
    int window[256] = {0}; // 记录窗口中每个字符出现的次数
    int needCount = 0;     // 记录 T 中不同字符的个数
    
    // 初始化 need
    for (int i = 0; t[i] != '\0'; i++) {
        if (need[t[i]] == 0) needCount++;
        need[t[i]]++;
    }
    
    int left = 0, right = 0;
    int valid = 0;  // 记录窗口中已经满足条件的字符个数
    int start = 0, minLen = INT_MAX;
    int len = strlen(s);
    
    while (right < len) {
        // 扩大窗口
        char c = s[right];
        right++;
        
        if (need[c] != 0) {
            window[c]++;
            if (window[c] == need[c]) {
                valid++;
            }
        }
        
        // 当所有字符都满足条件时，尝试缩小窗口
        while (valid == needCount) {
            // 更新最小子串
            if (right - left < minLen) {
                start = left;
                minLen = right - left;
            }
            
            // 缩小窗口
            char d = s[left];
            left++;
            
            if (need[d] != 0) {
                if (window[d] == need[d]) {
                    valid--;
                }
                window[d]--;
            }
        }
    }
    
    // 返回结果
    if (minLen == INT_MAX) {
        return "";
    }
    char* result = (char*)malloc((minLen + 1) * sizeof(char));
    strncpy(result, s + start, minLen);
    result[minLen] = '\0';
    return result;
}

这里有个关键点：valid 变量记录的是「已经满足条件的字符种类数」。当 valid == needCount 时，说明窗口已经覆盖了 T 中的所有字符。这时候我们尝试缩小窗口，找到最短的覆盖子串。

我曾经踩过的坑： 一开始我直接用 window[c] >= need[c] 来判断是否满足条件，结果发现重复字符会干扰判断。后来改用 valid 变量来计数，才解决了问题。细节决定成败啊。

五、知识体系总览

为了让你更直观地理解本章的知识结构，我画了一张图：

双指针与滑动窗口知识体系 双指针技巧 快慢指针 左右指针 链表环检测 有序数组去重 两数之和 II 反转字符串 滑动窗口 扩大窗口 → 缩小窗口 → 更新答案 最长无重复子串 最小覆盖子串 核心思想：用两个指针优化遍历，降低时间复杂度

六、总结与避坑指南

好了，我们来总结一下今天的内容：

  • 双指针：快慢指针用于「探索+确认」，左右指针用于「有序数组中的对撞」。
  • 滑动窗口：核心框架是「扩大窗口 → 缩小窗口 → 更新答案」，适用于子串/子数组问题。
  • 最长无重复子串：当窗口内出现重复字符时，缩小左边界。
  • 最小覆盖子串：用 valid 变量记录满足条件的字符种类数，当全部满足时尝试缩小窗口。
避坑指南：
  • 我曾经在滑动窗口的 while 循环里忘了更新 valid 变量，导致死循环。记住：缩小窗口时也要更新状态。
  • 我曾经在左右指针中，把 left < right 写成了 left <= right，导致数组越界。记住：边界条件要仔细检查。
  • 我曾经在快慢指针中，忘了处理空链表的情况。记住：边界条件永远要优先考虑。

双指针和滑动窗口，说白了就是「用空间换时间」的典型代表。它们不需要额外的数据结构，只需要两个指针和一点点思考。我建议你多练几道题，把框架刻在脑子里。下次遇到子串、子数组的问题，先想想能不能用滑动窗口解决。

好，今天就到这里。希望你能把这些技巧用到实际项目中，写出更高效的代码。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →