有一些创建辅助数组的技巧经常帮助我们解决数组问题。下面列出来。
前缀和数组，主要应用场景是原始数组不汇被修改的情况下，频繁查询某个区间的累加和。
差分数组，主要应用场景是频繁对原始数组的某个区间的元素进行增减。比如，给出数组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;
}
}
}
