螺旋数组
leetcode：
前缀和
对于一个数组，从第一个开始，每迭代到一个数，都把前面的和加到自身
作用：可以快速计算子数组之和（如果事先计算出数组的前缀和数组，则对于任意一个子数组，都可以在 O(1) 的时间内得到其元素和）
前缀和 在涉及计算区间和的问题时非常有用
let prefix = new Array(nums.length + 1).fill(0)
for (let i = 0; i < nums.length; i++) {
prefix[i + 1] = prefix[i] + nums[i]
}差分数组
对数组中相邻的元素两两计算差，得到差分数组：如
[1,2,3,4,5]的差分数组是：[1,1,1,1,1]
构造方式：
- 创建一个和原数组 arr 相同长度的新数组 diff，全部是 0
- 差分数组第一个元素和原数组第一个元素相同
- 对于 i =
1到n-1，差分数组 diff 的第 i 个元素为diff[i] = arr[i] - arr[i-1]
function createDiff(arr) {
let diff = new Array(arr.length).fill(0); // 差分数组
diff[0] = arr[0]
for (let i = 1; i < arr.length; i++) {
diff[i] = arr[i] - arr[i - 1]
}
return diff;
}作用：
可以将 对原始数组连续子数组的区间批量操作 转化为 对差分数组中两个数的操作
如：对
[1,2,3,4,5]中前四个数都加 2 变为[3,4,5,6,5]，差分数组变为[3,1,1,1,-1]相当于只需要对其差分数组的第一个值 +2，最后一个值 -2
差分数组还原成原数组：
只需要对差分数组求前缀和即可