0. 差分数组的概念：

常用于某个区间值都需加/减去a的问题。

1. 1094拼车

在这里插入图片描述

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        max_val = 0
        for i in range(len(trips)):
            max_val = max(max_val, trips[i][2])
        diff = [0]*(max_val+2)
        for i in range(len(trips)):
            diff[trips[i][1]] += trips[i][0]
            diff[trips[i][2]] -= trips[i][0]
        sum_val = 0   
        flag = True 
        for i in range(len(diff)):
            sum_val +=diff[i]
            if sum_val > capacity:
                flag = False
                break 
        return flag

2. 1109航班预定统计

在这里插入图片描述

class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        diff = [0]*(n+2)
        res = [0]*n
        sum_val = 0 
        for i in range(len(bookings)):
            diff[bookings[i][0]] += bookings[i][2]
            diff[bookings[i][1]+1] -= bookings[i][2]
        for i in range(1,n+1):
            sum_val+= diff[i]
            res[i-1] = sum_val
        return res

1674. 使数组互补的最少操作数

在这里插入图片描述

class Solution:
    def minMoves(self, nums: List[int], limit: int) -> int:
        diff = [0 for i in range(2*limit +2)]
        n = len(nums)
        for i in range(n//2):
            A = nums[i]
            B = nums[n-1-i]
            l = 2
            r = 2*limit
            diff [l] +=2
            diff[r+1] -=2
            l = 1 + min(A,B)
            r = limit + max(A,B)
            diff [l] -=1
            diff [r+1] +=1
            diff [A+B] -=1
            diff[A+B+1] +=1
        print(diff)    
        res = n    
        sum_val = 0
        for j in range(2,2+limit+1):
            sum_val += diff[j]
            res = min(res, sum_val)
        return res