如何优化多迭代整数数组操作性能？解决HackerRank数组操作问题

原代码问题分析 #

你的当前实现采用暴力遍历逻辑：对数组每个元素，逐一遍历所有查询判断是否在区间内累加值，时间复杂度为O(n*m)。当n和m同时达到数万级别时，计算量会呈指数级增长，直接导致超时。

优化方案：差分数组法 #

针对区间批量更新、求最终最大值的场景，差分数组是最优解法，能将时间复杂度降至O(m + n)，大幅提升性能。

核心原理 #

1. 构建长度为n+2的差分数组diff（预留额外空间避免处理边界时越界），初始值全为0。
2. 对每个查询[a, b, k]：
   • 在diff[a]处加上k，标记从位置a开始所有元素需要增加k
   • 在diff[b+1]处减去k，标记从位置b+1开始，之前的增量不再生效
3. 遍历差分数组计算前缀和，同时记录过程中的最大值，该值即为最终数组的最大值。

Swift 实现代码 #

func arrayManipulation(n: Int, queries: [[Int]]) -> Int {
    var diff = Array(repeating: 0, count: n + 2) // 用n+2避免b+1越界
    
    for query in queries {
        let a = query[0]
        let b = query[1]
        let k = query[2]
        diff[a] += k
        diff[b + 1] -= k
    }
    
    var currentMax = 0
    var currentSum = 0
    for i in 1...n {
        currentSum += diff[i]
        if currentSum > currentMax {
            currentMax = currentSum
        }
    }
    
    return currentMax
}

示例验证 #

用你提供的测试用例：

• n=5，queries=[[2,4,4],[3,4,5]]
• 初始diff数组：[0,0,0,0,0,0,0]
• 处理第一个查询：diff[2] +=4 → diff[2]=4；diff[5] -=4 → diff[5]=-4
• 处理第二个查询：diff[3] +=5 → diff[3]=5；diff[5] -=5 → diff[5]=-9
• 计算前缀和：
  • i=1: currentSum=0 → max=0
  • i=2: currentSum=0+4=4 → max=4
  • i=3: currentSum=4+5=9 → max=9
  • i=4: currentSum=9+0=9 → max保持9
  • i=5: currentSum=9+(-9)=0 → max保持9
• 最终返回9，和原代码结果一致，但性能提升显著。

性能对比 #

• 原代码：n=4000，m=30000时，需执行4000*30000=120,000,000次循环
• 优化后代码：仅需执行30000+4000=34,000次循环，计算量减少99.9%

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