Swift 解法详解：LeetCode 370《区间加法》

摘要

在日常开发中，我们经常会遇到类似“批量修改区间”的场景，比如给一批用户的积分统一加值，或者对一个时间段的数据统一做调整。这类问题如果逐个处理，效率会非常低。LeetCode 370《区间加法》就是一个这样的模型：我们要对一个数组的区间进行多次加法操作，最后返回修改后的数组。

这道题其实是“差分数组”技巧的典型应用，非常适合拿来作为算法思路的积累。

描述

题目要求：

给你一个长度为 n 的数组，初始时所有元素都是 0。再给你一系列更新操作，每个操作由 [startIndex, endIndex, inc] 三个数构成，表示从下标 startIndex 到 endIndex（包含两端）之间的所有元素都增加 inc。

最终返回修改后的数组。

示例 1：

输入: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
输出: [-2,0,3,5,3]
解释: 
初始数组: [0,0,0,0,0]
更新 [1,3,2] -> [0,2,2,2,0]
更新 [2,4,3] -> [0,2,5,5,3]
更新 [0,2,-2] -> [-2,0,3,5,3]

题解答案

如果我们天真地写法，每次更新就对 [startIndex, endIndex] 之间的每个元素都加上 inc，那在最坏情况下时间复杂度会达到 O(k·n)，k 是操作次数，n 是数组长度。这在数据量大的时候会非常慢。

正确的思路是用 差分数组（Difference Array）：

• 差分数组的本质是用一个辅助数组 diff 来记录“变化趋势”。

• 当我们要对 [l, r] 区间加 inc 时，只需要：

  • diff[l] += inc
  • 如果 r + 1 < n，则 diff[r+1] -= inc

• 最后通过一次前缀和，把 diff 还原成最终的数组。

这样每次操作只需要 O(1)，最终再做一次前缀和 O(n) 就能得到答案。

题解代码分析

下面是 Swift 的完整代码实现：

import Foundation

class Solution {
    func getModifiedArray(_ length: Int, _ updates: [[Int]]) -> [Int] {
        var diff = Array(repeating: 0, count: length)
        
        // 应用差分更新
        for update in updates {
            let start = update[0]
            let end = update[1]
            let inc = update[2]
            
            diff[start] += inc
            if end + 1 < length {
                diff[end + 1] -= inc
            }
        }
        
        // 通过前缀和恢复原数组
        var result = Array(repeating: 0, count: length)
        var runningSum = 0
        for i in 0..<length {
            runningSum += diff[i]
            result[i] = runningSum
        }
        
        return result
    }
}

// MARK: - Demo 演示
let solution = Solution()
let length = 5
let updates = [[1,3,2],[2,4,3],[0,2,-2]]
let result = solution.getModifiedArray(length, updates)
print(result) // 输出: [-2, 0, 3, 5, 3]

代码拆解

1. 初始化差分数组

   • diff 和原数组长度一样，初始全为 0。
   • 它不是最终结果，而是用来记录“区间的变化”。

2. 应用更新

   • 每个更新 [l, r, inc] 只改动 diff[l] 和 diff[r+1]。
   • 这样就避免了对区间里所有元素逐个修改。

3. 恢复结果

   • 最后用一个变量 runningSum 记录前缀和，逐步把 diff 变成最终结果。

示例测试及结果

运行上面的 Demo：

初始数组: [0,0,0,0,0]
更新 [1,3,2] -> [0,2,2,2,0]
更新 [2,4,3] -> [0,2,5,5,3]
更新 [0,2,-2] -> [-2,0,3,5,3]

输出: [-2, 0, 3, 5, 3]

和题目给的结果完全一致。

时间复杂度

• 更新阶段：每个操作只需要 O(1)，k 次操作就是 O(k)。
• 恢复数组：前缀和需要 O(n)。
• 总体复杂度：O(n + k)。

这比逐个更新 O(n·k) 的复杂度要高效得多。

空间复杂度

• 只用了一个和原数组等长的差分数组 diff，所以空间复杂度是 O(n)。

总结

这道题本质上是考差分数组的应用，常见于 区间更新 的场景。

思路要点：

• 直接更新区间效率低，要用“变化趋势”的方式去优化。
• 差分数组的妙处在于只记录“区间开始变化”和“区间结束恢复”。
• 最后一次性还原出结果，既高效又简洁。

在实际开发中，这种技巧同样很有用。比如：

• 日志系统里批量修改某些时间段的计数。
• 数据库里批量更新一批连续记录。
• 游戏里给一群玩家（按等级区间）加经验值。

差分数组就是这类问题的通用解法，非常值得掌握。