如何用指针实现C++数组的滑动窗口高效子数组处理技术

P粉602998670

发布时间：2025-07-29 11:07:01

1062人浏览过

来源于php中文网

原创

指针在c++++中实现滑动窗口的核心在于利用指针的自增/自减操作来模拟窗口的滑动，从而避免不必要的数组复制，提高效率。1. 通过指针直接操作内存地址，减少数据复制开销，尤其适用于大型数组；2. 初始计算窗口和后，在滑动时只需减去离开窗口的元素并加上新进入窗口的元素，减少重复计算；3. 在字符串处理中，滑动窗口可用于查找最小子串问题，虽然未直接使用原始指针，但left和right变量可视为指针抽象；4. 指针实现的优势包括高效性和灵活性，但也存在易出错、可读性差和调试困难等局限性。

如何用指针实现C++数组的滑动窗口高效子数组处理技术

指针在C++中实现滑动窗口，核心在于利用指针的自增/自减操作来模拟窗口的滑动，避免不必要的数组复制，从而提高效率。尤其是在处理大型数组时，这种方法优势明显。

解决方案

滑动窗口的核心思想是维护一个固定大小的窗口，通过移动窗口的起始和结束位置，来遍历数组的所有可能的子数组。用指针实现，可以避免每次窗口滑动都进行数组复制，而是直接修改指针指向的位置。

立即学习“C++免费学习笔记（深入）”；

#include 
#include 

using namespace std;

// 计算滑动窗口内的元素和
int calculateSum(int* start, int* end) {
    int sum = 0;
    while (start <= end) {
        sum += *start;
        start++;
    }
    return sum;
}

int main() {
    vector arr = {1, 3, -1, -3, 5, 3, 6, 7};
    int windowSize = 3;
    int n = arr.size();

    if (n < windowSize) {
        cout << "窗口大小大于数组大小，无法滑动。" << endl;
        return 1;
    }

    int* windowStart = arr.data(); // 指向数组起始位置的指针
    int* windowEnd = windowStart + windowSize - 1; // 指向窗口结束位置的指针

    // 循环遍历数组，滑动窗口
    while (windowEnd < arr.data() + n) {
        // 计算当前窗口的和
        int currentSum = calculateSum(windowStart, windowEnd);
        cout << "窗口和: " << currentSum << endl;

        // 移动窗口
        windowStart++;
        windowEnd++;
    }

    return 0;
}

这段代码展示了基本原理。arr.data()获取数组首地址，然后通过指针的加减运算来确定窗口的起始和结束位置。calculateSum函数计算当前窗口的和。

副标题1 如何优化滑动窗口的求和操作，避免重复计算？

最朴素的滑动窗口实现，每次滑动都要重新计算窗口内所有元素的和，这显然存在重复计算。优化方法是，在窗口滑动时，只减去离开窗口的元素，加上进入窗口的元素。

AdsGo AI

全自动 AI 广告专家，助您在数分钟内完成广告搭建、优化及扩量

下载

#include 
#include 

using namespace std;

int main() {
    vector arr = {1, 3, -1, -3, 5, 3, 6, 7};
    int windowSize = 3;
    int n = arr.size();

    if (n < windowSize) {
        cout << "窗口大小大于数组大小，无法滑动。" << endl;
        return 1;
    }

    int* windowStart = arr.data();
    int* windowEnd = windowStart + windowSize - 1;

    // 初始窗口的和
    int currentSum = 0;
    for (int i = 0; i < windowSize; ++i) {
        currentSum += arr[i];
    }
    cout << "初始窗口和: " << currentSum << endl;


    // 循环遍历数组，滑动窗口
    while (windowEnd < arr.data() + n -1) { //注意这里，循环条件要减1，避免越界
        // 移动窗口
        windowStart++;
        windowEnd++;

        // 更新窗口和：减去离开窗口的元素，加上进入窗口的元素
        currentSum = currentSum - * (windowStart-1) + *windowEnd;
        cout << "窗口和: " << currentSum << endl;
    }

    return 0;
}

这种方式显著减少了计算量，尤其是在窗口大小比较大的时候。

副标题2 指针滑动窗口在处理字符串子串问题中的应用？

滑动窗口在字符串处理中非常常见，比如查找包含特定字符的最小子串。

#include 
#include 
#include 

using namespace std;

string minWindow(string s, string t) {
    unordered_map need, window;
    for (char c : t) need[c]++;

    int left = 0, right = 0;
    int valid = 0; // 满足need条件的字符个数
    int start = 0, len = INT_MAX;

    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        right++;
        // 更新窗口数据
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c])
                valid++;
        }

        // 判断左侧窗口是否要收缩
        while (valid == need.size()) {
            // 在这里更新最小覆盖子串
            if (right - left < len) {
                start = left;
                len = right - left;
            }

            // d 是将移出窗口的字符
            char d = s[left];
            left++;
            // 更新窗口数据
            if (need.count(d)) {
                if (window[d] == need[d])
                    valid--;
                window[d]--;
            }
        }
    }
    // 如果没有找到符合条件的子串，则返回空字符串
    return len == INT_MAX ? "" : s.substr(start, len);
}


int main() {
    string s = "ADOBECODEBANC";
    string t = "ABC";
    string result = minWindow(s, t);
    cout << "最小覆盖子串: " << result << endl; // 输出: BANC
    return 0;
}

这个例子使用 unordered_map 来记录需要的字符和窗口中已有的字符，通过滑动窗口来找到包含所有目标字符的最小子串。虽然这里没有直接使用原始指针，但left和right变量可以看作是指针的抽象，控制着窗口的滑动。

副标题3 使用指针实现滑动窗口的优势和局限性？

优势：