话不多说,直接看差别,下面用的暴力法,上面是用差分法,数学问题,其实也没太看懂具体什么原理
看程序,只能有一点粗浅的认识
class Solution { public int[] corpFlightBookings(int[][] bookings, int n) { int[] nums = new int[n]; for(int[] booking:bookings){ nums[booking[0]-1] += booking[2]; if(booking[1] < n){ nums[booking[1]] -= booking[2]; } } for(int i = 1;i < n; i++){ nums[i] += nums[i-1]; } return nums; } }
首先看第五行,只把所有要变化区间的头增加这些值
第七行,是将区间变化区间的末端后一个元素减掉增加值
再看第十行,将现有的数组所有元素后面的加上前一个元素的值,前面已经对末端后一个提前减值,所以不会有多加的现象