如何为数组每个索引i递增其自身及左右各K个元素（含边界检查）

原代码是遍历数组时仅对当前索引元素自增，现在需要修改为：遍历每个索引i时，对i本身及其左右最多K个元素（即区间[i-K, i+K]）执行自增操作，同时处理数组边界（超出数组范围的索引忽略）。

方法一：暴力遍历（直观易理解） #

直接对每个i计算有效区间，然后遍历区间内的元素执行自增。这种方法逻辑简单，但时间复杂度为O(N*K)，当K较大时效率较低。

代码实现（C语言）：

for (int i = 0; i < N; i++) {
    // 计算有效区间的起始和结束索引
    int start = max(0, i - K);
    int end = min(N - 1, i + K);
    // 遍历区间内的所有元素并自增
    for (int j = start; j <= end; j++) {
        arr[j]++;
    }
}

方法二：差分数组优化（高效实现） #

如果数组规模较大或K值很高，暴力法的效率会很差，这时可以用差分数组来将时间复杂度降到O(N)。差分数组的核心思想是通过记录区间的增减变化，最后通过前缀和得到最终结果。

代码实现（C语言）：

// 创建差分数组，大小设为N+1避免处理边界越界
int diff[N + 1] = {0};

for (int i = 0; i < N; i++) {
    int L = max(0, i - K);
    int R = min(N - 1, i + K);
    // 标记区间[L, R]的起始加1
    diff[L]++;
    // 标记区间结束的下一位减1（如果不超出数组范围）
    if (R + 1 < N) {
        diff[R + 1]--;
    }
}

// 计算前缀和，将结果还原到原数组
arr[0] = diff[0];
for (int i = 1; i < N; i++) {
    arr[i] = arr[i - 1] + diff[i];
}

两种方法对比 #

• 暴力法：实现简单，适合小规模数组或K较小的场景，时间复杂度O(N*K)。
• 差分数组：实现稍复杂，但效率极高，适合大规模数组或K较大的场景，时间复杂度O(N)。

内容的提问来源于stack exchange，提问作者sznailc