LC724
寻找数组的中心下标
前缀和 · 中心下标可视化:前缀和/积找 pivot 使左右前缀和相等。
时间 O(n)空间 O(1)
题目1 / 9
题目与输入建立输入、目标与算法心智
枢轴:左侧和等于右侧和
正在加载算法场景...
当前发生了什么
找 pivot 使左右前缀和相等。
机器状态
prefix、i。
为什么正确
prefix[i]=sum[0..i);检查 prefix[i]==prefix[n]-prefix[i+1]。
不变量
左侧和=prefix[i],右侧=total-prefix[i+1]。
面试怎么说
前缀和 O(n)。
人类输入
找 pivot 使左右前缀和相等。
机制
prefix[i]=sum[0..i);检查 prefix[i]==prefix[n]-prefix[i+1]。
机器状态
prefix、i。
可观察结果
pivot 下标 3(若存在)。
不变量
- · 左侧和=prefix[i],右侧=total-prefix[i+1]。
常见误区
- · 无 pivot 返回 -1。
迁移练习
- · LC560 和为 K
- · LC1480 运行和
面试怎么答
前缀和 O(n)。