二维数组处理效率过低，HackerRank Crush问题优化方案求问

你的代码超时的核心原因是时间复杂度太高：原方案采用嵌套循环，每个查询都要遍历区间内的所有元素，时间复杂度为O(m*n)。当题目中n（数组长度）达到1e7、m（查询次数）达到1e5时，总运算量会突破1e12，远远超出时间限制。

优化方案：差分数组技巧 #

通过差分数组可以将区间更新操作从O(n)压缩到O(1)，整体时间复杂度降为O(m + n)，完全适配大规模数据场景。

原理说明

对于区间[l, r]增加数值k，不需要逐个更新区间内元素，只需在差分数组上做两个操作：

1. 在差分数组的l位置加上k
2. 在差分数组的r+1位置减去k（如果r+1不超过数组长度）

最后遍历差分数组计算前缀和，前缀和的过程就是还原原数组的过程，同时记录过程中的最大值即可。

优化后的代码

long arrayManipulation(int n, vector<vector<int>> queries) {
    vector<long> diff(n + 2, 0); // 额外多开两个位置，避免处理r+1越界的边界情况
    
    for (auto& query : queries) {
        int left = query[0];
        int right = query[1];
        long val = query[2];
        
        diff[left] += val;
        if (right + 1 <= n) {
            diff[right + 1] -= val;
        }
    }
    
    long max_value = 0;
    long current_sum = 0;
    for (int i = 1; i <= n; ++i) {
        current_sum += diff[i];
        if (current_sum > max_value) {
            max_value = current_sum;
        }
    }
    
    return max_value;
}

代码说明 #

• 差分数组diff的长度设为n+2，是为了避免当right等于n时，right+1超出数组范围的问题，省去额外的边界判断逻辑
• 遍历查询时仅需两次数组赋值操作，将每个查询的时间成本从O(n)降到O(1)
• 最后计算前缀和的过程是O(n)，整体时间复杂度为O(m + n)，可以轻松通过所有测试用例

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