有一些创建辅助数组的技巧经常帮助我们解决数组问题。下面列出来。

• 前缀和数组，主要应用场景是原始数组不汇被修改的情况下，频繁查询某个区间的累加和。

• 差分数组，主要应用场景是频繁对原始数组的某个区间的元素进行增减。比如，给出数组nums，我做了下面一系列操作：给区间【3。。5】全部加1，给区间【4。。8】全部减2。。。整完之后，数组变成了多少。

关键点

• 还是老一套，以空间换时间。
• 问题转化，通过一个辅助的中间数组变量获得问题的答案。
• 有时候需要结合辅助数组做一些改变，比如560题，辅助数组就是一个hash表，目的就是为了记住前面某个前缀和已经出现了多少次。

代码

//t560
class Solution {
    public int subarraySum(int[] nums, int k) {
         int[] preSum = new int[nums.length+1]; //i-th store preSum 0-i-1;
        Map<Integer, Integer> memo = new HashMap<>(); // store preSum frequency
        int ret = 0;
        preSum[0] = 0;
        memo.put(0, 1);
        
        for(int i = 1; i < nums.length+1; i++){
            preSum[i]  = preSum[i-1] + nums[i-1];
            int need = preSum[i] - k;
            //System.out.println(need);
            if(memo.containsKey(need)){
                ret += memo.get(need);
            }        
            
            memo.put(preSum[i], memo.getOrDefault(preSum[i], 0) + 1);
        }
        
        return ret;
    }
}

// t1109
class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] res = new int[n];
        int[] diff = new int[n];
        Arrays.fill(diff, 0);
        
        for(int[] book : bookings){
            increment(book[0] - 1, book[1] - 1, book[2], diff);
        }
        
        res[0] = diff[0];
        for(int i = 1; i < n; i++){
            res[i] = res[i-1] + diff[i];
        }
        
        return res;
        
    }
    
    //差分数组
    
    private void increment(int begin, int end, int value, int[] diff){
        diff[begin] += value;
        if(end + 1 < diff.length){
            diff[end + 1] -= value;
        }
    }    
}