Day 7 差分数组：370. 区间和，1109. 航班预订统计，1094. 拼车

前缀和

• 差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。

  
  
• 如果你想对区间 nums[i..j] 的元素全部加 3，那么只需要让 diff[i] += 3，然后再让 diff[j+1] -= 3 即可：
  

370. Range Addition

• 思路
  • example
  • 前缀和数组与差分数组的相互转换

diff[0] = nums[0]
diff[i] = nums[i] - nums[i-1]

• 复杂度. 时间：O(n), 空间: O(n)

class Solution:
    def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:
        # diff[i] = nums[i] - nums[i-1], diff[0] = nums[0]
        diff = [0 for _ in range(length)]
        for update in updates:
            start, end, increment = update[0], update[1], update[2]
            diff[start] += increment 
            if end + 1 < length:
                diff[end+1] -= increment 
        # nums[i] = nums[i-1] + diff[i]
        nums = [0 for _ in range(length)]
        nums[0] = diff[0]
        for i in range(1, length):
            nums[i] = nums[i-1] + diff[i]
        return nums  

1109. Corporate Flight Bookings

• 思路
  • example
  • 转化为差分问题
• 复杂度. 时间：O(?), 空间: O(?)

class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        diff = [0 for _ in range(n)]
        for i, j, inc in bookings:
            i -= 1
            j -= 1 # shift index
            diff[i] += inc  
            if j < n-1:
                diff[j+1] -= inc  
        nums = [0 for _ in range(n)]
        nums[0] = diff[0]
        for i in range(1, n):
            nums[i] = nums[i-1] + diff[i]
        return nums  

1094. Car Pooling

• 思路
  • example
  • 1 <= trips.length <= 1000, 0 <= fromi < toi <= 1000
• 复杂度. 时间：O(?), 空间: O(?)

from_i,..., to_i-1

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        diff = [0 for _ in range(1001)]
        for inc, start, end in trips:
            end -= 1 # !!! 在这里下车
            diff[start] += inc  
            if end < 1000:
                diff[end+1] -= inc  
        nums = [0 for _ in range(1001)]
        nums[0] = diff[0]
        if nums[0] > capacity:
            return False 
        for i in range(1, 1001):
            nums[i] = nums[i-1] + diff[i]
            if nums[i] > capacity:
                return False 
        return True