0x00 前缀和

1. 关键字：整数数组、中心下标、下标左侧之和等于右侧之和、求中心下标

题目： https://leetcode.cn/problems/find-pivot-index/description/ 可使用前缀和进行计算：

前缀和基本公式


const arr = [1,2,3,4,5]
const n = arr.length;
const prefixSum = new Array(n); // 创建一个与原始数组相同长度的累加和数组

// 初始化累加和数组的第一个元素为原始数组的第一个元素 prefixSum[0] = arr[0];

// 使用循环计算累加和数组的其他元素 for (let i = 1; i < n; i++) { prefixSum[i] = prefixSum[i - 1] + arr[i]; }

console.log(prefixSum); // [1, 3, 6, 10, 15]

- 求右侧公式：
```js
// 数组总和 - 前缀和 - 中心下标
// prefixSum === total - arr[i] - prefixSum

求中心下标公式推导：

// 只要在循环中满足以下公式，那么i就为中心下标，否则判断该数组不存在左右值相等的中心下标
// prefixSum === total - arr[i] - prefixSum
// => 2 * prefixSum + arr[i] === total

已知题目有中心下标，且左侧与右侧之和相等，那么只需遍历下标不断求左侧前缀和，再对右侧进行公式


const arr = [1, 7, 3, 6, 5, 6]; 
const total = arr.reduce((a,b) => a + b, 0);
let prefixSum = 0;
let i = 0;
// 求中心下标
for (; i < arr.length; i++) {
if (2 * prefixSum + arr[i] === total) {
break;
}
prefixSum += arr[i]
}
console.log(i); // 3

TinyScript / notes

从零收集算法概念 #5

0x00 前缀和

1. 关键字：整数数组、中心下标、下标左侧之和等于右侧之和、求中心下标

0x01 动态规划

1. 关键内容：