Prefix Sum

本学习计划适用于那些想要准备技术面试但不确定他们应该关注哪些问题的人。这些问题经过精心策划，因此 Level 1和 Level 2 将指导初级和中级用户解决涵盖大多数中端公司面试所需的数据结构和算法的问题。而 Level 3 用来帮助以顶级公司为目标的学习小伙伴。

本学习计划的题目小编解答在英文版 LeetCode 中尽可能超越 100% 提交 。

---

前缀和（Prefix sum）是算法题中比较实用的一种技巧，当算法题的背景是整型数组且出现 “子数组和” 或者 “连续的子数组” 既可以考虑使用前缀和来求解会得到不错的效果。

第一题：一维数组的动态和

image-20221003195616924

从题目的解释中也表达的是一个连接累加前 n 个数的过程。细心的读者可以发现它也可以被归类到动态规划题目中，因为它可以得到状态转移方程：

image-20221003202208029

这其实也同样满足 Prefix Sum 的技巧。如下动图显示的是如何利用结果与数组来动态计算最终结果数组。

running-sum

public class RunningSumOf1dArray {
    public int[] runningSum(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            nums[i] = nums[i] + nums[i-1];
        }

        return nums;
    }
}

第二题：寻找数组的中心下标

image-20221003202809473

从题目中可知要找的是一个 idx，使得在 idx 的左边和与右边各相等。那假设左（右）边的各为 sum 的话，那么就是整个数组的和为：

image-20221003203626254

然后就可以进行如下推导：

image-20221004092908211

于是，如果我们先计算出总和，然后第二次循环累加时算为左值，那么右值就是上述式子了，于是就可以判断是否能找到这样的一个 idx 了。

public class FindPivotIndex {
    public int pivotIndex(int[] nums) {
        int leftSum = 0, rightSum = 0;
        // 计算总和
        for (int num : nums) {
            rightSum += num;
        }

        for (int i = 0; i < nums.length; i++) {
            // 右值：rightSum - leftSum - nums[i]
            if (leftSum == rightSum - leftSum - nums[i]) {
                return i;
            }
            // 左值：nums[0] ... nums[i-1]
            leftSum += nums[i];
        }

        return -1;
    }
}

---

代码仓库：https://github.com/chaffz/leetcode-java