1109. 航班预订统计 --前缀和 和差分

换一种思路理解题意，

• 将问题转换为：某公交车共有n站，第i条记录bookings[i] = [i, j, k]表示在i站上车k人，乘坐到j站，在j+1站下车，需要按照车站顺序返回每一站车上的人数
• 根据1的思路，定义counter[]数组记录每站的人数变化，counter[i]表示第i+1站。遍历bookings[]：bookings[i] = [i, j, k]表示在i站增加k人即counters[i-1] += k，在j+1站减少k人即counters[j] -= k
• 遍历（整理）counter[]数组，得到每站总人数： 每站的人数为前一站人数加上当前人数变化counters[i] += counters[i - 1]

class Solution {
        public int[] corpFlightBookings(int[][] bookings, int n) {
            int ans [] = new int [n];                                          //请注意这里不能改n的值 所以当e = 5时 并不用继续处理
            int m  = bookings.length;
            for(int i = 0 ; i <  m ; i++) {
                int s = bookings[i][0];
                int e = bookings[i][1];
                int k = bookings[i][2];
                ans[s-1] += k;
                if(e < n )                                                        //与上面做呼应
                    ans[e] -= k;
            }
            for(int i = 1 ; i < n ; i++) {                                      //思路太妙了
                ans[i] += ans[i-1];
            }
        return ans ;
    }
}

本题数据范围是20000，直接加的暴力方法会超时，需要优化到线性时间才行，考虑前缀和或者线性扫描，本质是一样的。题目中bookings每一项给出了一个区间，包含区间的开始位置、结束位置和区间值，当我们从左到右遍历答案数组时，进入这个区间就要加上这个区间的值，出这个区间就要减去这个区间的值，所以我们只需要用字典或者在数组中记录一下区间端点和相应的值，再从左到右扫描一遍数组即可。