力扣 1109. 航班预订统计
这里有 n 个航班，它们分别从 1 到 n 进行编号。
有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。
请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。
方案一：通过差分计算座位数的增减，然后将其在进行前缀求和（对差分数组的求和等于原数组）。
func corpFlightBookings(bookings [][]int, n int) []int {
// 因为下标是 1 开始的，并且基于差分求解，会用到正常下标往后一位，所以需要加 2
diff := make([]int, n + 2)
for _, booking := range bookings {
first, last, seats := booking[0], booking[1], booking[2]
// 根据差分原理对当前坐标和结尾坐标的后一个进行操作
diff[first], diff[last + 1] = diff[first] + seats, diff[last + 1] - seats
}
// 对差分求前缀和即为原数组
for i := 1; i <= n; i++ {
diff[i] += diff[i - 1]
}
// 界定结果上下界
return diff[1:n+1]
}
- 时间复杂度：O(n)，因为需要遍历 bookings 求的差分后再进行前缀和，所以时间复杂度为 O(n)。
- 空间复杂度：O(n)，因为使用了长度为 n + 2 的辅助数组保存差分结果，所以空间复杂度为 O(n)。