前缀和算法进阶：中心下标与子数组求和

一、724. 寻找数组的中心下标

题目解析

这道题，给定数组 nums，要求我们找出这个数组的中心下标。

**中心下标：**指左侧所有元素的和等于右侧所有元素的和。

如果存在多个中心数组下标，就返回最左侧的中心数组下标。

算法思路

暴力解法：

对于这道题，要找出数组的中心下标，暴力解法就是遍历数组，依次判断该位置中心下标（左侧所有元素等于右侧所有元素）。

对于暴力解法，遍历数组 nums；

遍历到 i 位置时，判断该位置是否是中心下标，也就是该位置左侧所有元素是否等于右侧所有元素。

优化：

暴力解法要遍历数组，遍历到 i 位置时还需求左侧所有元素的和、右侧所有元素的和，就还需再遍历数组来求。

时间复杂度就是 O(n)；对于遍历数组的每一个元素，依次判断该位置是否是中心下标，这里进行不了优化；

那就来看：遍历到 i 位置时，求左侧所有元素的和、右侧所有元素的和

在暴力解法中，我们就遍历 i 位置左侧的所有元素，求左侧所有元素的和；遍历 i 位置右侧所有元素的和，求右侧所有元素的和。

我们可不可以使用更简单的方法来拿到 i 位置所有元素的和？

当然是可以的，我们可以预先处理前缀和与后缀和数组，这样就可以以 O(1) 的时间复杂度拿到 i 位置左侧所有元素的和、i 位置右侧所有元素的和。

**前缀和：**预处理前缀和、后缀和数组：遍历到 i 位置时需要 i 位置前面所有元素的和，i 位置后面所有元素的和；这里预先处理前缀和数组 f 和后缀和数组 g

前缀和数组 f：f[i] 表示区间 [0,i-1] 中所有元素的和。（i 位置前面所有元素的和）

后缀和数组 g：g[i] 表示区间 [i+1 , n-1] 中所有元素的和。（i 位置后面所有元素的和）

**使用前缀和、后缀和数组：**有了前缀和、后缀和数组，在遍历到 i 位置时只需判断 f[i] 是否等于 g[i] 即可。如果 f[i] == g[i]，就表示 i 位置是一个中心位置，返回该位置下标 i 即可。如果 f[i] != g[i]，就表示 i 位置不是应该中心位置，继续向后遍历即可。

预处理前缀和：

这里 f[i] 表示的是 [0 , i-1] 中所有元素的和，所以在填表时从 1 开始向后填表；f[i] = f[i-1] + nums[i];

g[i] 表示的是 [i+1 , n-1] 中所有元素的和，所以在填表时从 n-2 开始向前填表；g[i] = g[i+1] + nums[i];

**初始化：**在填 f[1] 时会用到 f[0]，而 f[0] 表示的是 [0,-1] 中所有元素的和，该区间不存在。所以初始化 f[0] = 0

在填 g[n-2] 时会用到 g[n-1]，而 g[n-1] 表示 [n,n-1] 中所有元素的和，该区间不存在、所以初始化 g[n-1] = 0

代码实现

class Solution {
public:
    int f[10002]; // [0 , i-1]
    int g[10002]; // [i+1 , n-1]
    int pivotIndex(vector<int>& nums) {
        int n = nums.size();
        f[0] = 0;
        g[n] = 0;
        for(int i = 1; i <= n; i++) f[i] = f[i - 1] + nums[i - 1];
        for(int i = n - 2; i >= 0; i--) g[i] = g[i + 1] + nums[i + 1];
        for(int i = 0; i < n; i++) {
            if(f[i] == g[i]) return i;
        }
        return -1;
    }
};

二、238. 除自身以外数组的乘积

题目解析

对于这道题，给定一个数组 nums，要求出数组 answer；

其中 anwser[i] 表示 nums 数组中除了 nums[i] 以外的所有数的乘积。

算法思路

对于这道题，要返回数组 answer，其中 answer[i] 表示除了 nums[i] 以外的所有数的乘积。

那也就是说，我们需要求出 nums 中每一个元素对应的 answer[i]。

暴力解法：

遍历整个数组 nums，遍历到 i 位置时，再遍历整个数组计算除了 i 位置之外其他所有数的乘积。

这里时间复杂度就是 O(n^2)。

优化

这里当我们遍历到 i 位置时，暴力解法就是再次遍历数组，来计算除了 i 以外的所有数的乘积。

也就是以 O(n) 的时间复杂度来获取除了 i 位置意外所有数的乘积。

这里我们可不可以通过预先处理，来直接就可以拿到除了 i 位置意外的所有数的乘积。

这里，当遍历到 i 位置时，我们可以发现 i 位置把整个数组分成了两部分：

一部分是区间 [0 , i-1]、另一部分则是区间 [i+1 , n-1]；

那我们只要拿到区间 [0 , i-1] 中所有数的乘积，区间 [i+1 , n-1] 中所有数的乘积那就可以直接计算除了 i 位置以外所有数的乘积。

前缀和 (积)

所以，我们就可以通过预先处理前缀积数组，在遍历到 i 位置时，就可以以 O(1) 的时间复杂度获取到除了 i 位置以外的所有数的积。

前缀积数组：f[i] 表示区间 [0 , i-1] 中所有数的积

后缀积数组：g[i] 表示区间 [i+1 , n-1] 中所有数的积

预处理前/后缀积数组：

前缀积：f[i] = f[i-1] * nums[i-1]

后缀积：g[i] = g[i+1] * nums[i+1]

使用前/后缀积数组：

在遍历到 i 位置时，除 i 位置以外的所有数的乘积 sum = f[i] * g[i]。（这里就可以使用 O(1) 的时间复杂度获取除 i 位置以外的所有数的乘积）

**初始化：**在预处理前缀积数组时，f[1] 会用到 f[0]，而区间 [0,-1] 显然不存在；为了不影响前缀积数组中的其他数，将 f[0] 初始化为 1。在预处理后缀积数组时，g[n-2] 会用到 g[n-1]，而区间 [n , n-1] 显然不存在；为了不影响后缀积中的其他数，将 g[n-1] 初始化为 1。

细节：

前缀积：前缀积数组 f[i] 表示区间 [0 , i-1] 中所有数的积，在预处理时要处理到 n 位置。（从前往后）

后缀积：后缀积数组 g[i] 表示区间 [i+1 , n-1] 中所有数的积，在预处理时就要处理到 0 位置。（从后往前）

代码实现

class Solution {
public:
    int f[100001];
    int g[100001];
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        f[0] = g[n - 1] = 1;
        for(int i = 1; i <= n; i++) {
            f[i] = f[i - 1] * nums[i - 1];
        }
        for(int i = n - 2; i >= 0; i--) {
            g[i] = g[i + 1] * nums[i + 1];
        }
        vector<int> ret(n);
        for(int i = 0; i < n; i++) {
            ret[i] = f[i] * g[i];
        }
        return ret;
    }
};

三、560. 和为 K 的子数组

题目解析

对于这道题，给定一个数组 nums 和一个整数 k

我们要求在 nums 数组中存在多少个和为 k 的子数组。

注意：这道题中给的的数据范围：-1000 <= nums[i] <= 1000

算法思路

暴力解法：

首先，对于这道题，暴力解法就是枚举：枚举所有的子数组，然后找出和为 k 的子数组的个数。

枚举所有子数组，以 i 为起始位置，j 为结束位置的子数组；

求出子数组的和，然后找到子数组和为 k 的个数。

前缀和：

在暴力解法枚举所有子数组中，本质就是先固定 i 位置，再枚举以 i 位置为起始位置的子数组，寻找和为 k 的子数组。

那我们也可以先固定 i 位置，再枚举所有以 i 位置为结束位置的子数组，然后在这些子数组中，找到和为 k 的子数组。

所以，我们在遍历数组时，就可以先固定 i 位置，再枚举以 i 位置为结束位置的所有子数组，在这些子数组中找和为 k 的子数组

那如何去找呢？

在遍历到 i 位置时，我们要找以 i 位置为结束位置的所有子数组这和为 k 的子数组的个数；

那我们就可以将问题转换以下：在区间 [0 , i] 中寻找前缀和为 sum - k 的个数。

所以，我们就可以在区间 [0 , i-1] 中找前缀和为 sum - k 的个数，找到的就是以 i 为结束位置、和为 k 的子数组的个数。

所以，现在我们预处理处一个前缀和数组，然后遍历 nums 数组，遍历到 i 位置时就要在区间 [0 , i-1] 中找前缀和等于 sum - k 的数量

但是这样来解的话，时间复杂度貌似还不如暴力解法啊，时间复杂度为 O(n^2 + n) 啊。

hash 表优化：

我们知道了使用前缀和如何去求以 i 位置为结束位置、和为 k 的子数组的个数；但是时间复杂度却不如暴力解法。

原因就是：在遍历 i 位置时我们还需要去遍历区间 [0 , i-1] 中的所有前缀和，才能够知道前缀和为 sum - k 的数量。

这里要求前缀和为 sum - k 的数量，就可以使用 hash 表来优化：

在遍历到 i 位置时，hash 表中存储区间 [0 , i-1] 中所有前缀和以及前缀和出现的次数。（这样我们就可以直接获取前缀和为 sum - k 的数量。

细节问题：hash 表中存储的是区间 [0 , i-1] 中所有的前缀和以及前缀和出现的次数；所以在遍历数组的过程中，依次统计前缀和出现的次数。初始情况下 hash 中一个存在前缀和为 0，出现次数为 1 的元素：(0 , 1)；如果整个数组的和为 k，只有存在 (0 , 1) 才能统计上这种情况。使用一个数 sum 来代替整个前缀和数组；这里没有必要去预处理一个前缀和数组，只需用 sum 即可代替；sum 表示遍历到 i 位置时，区间 [0 , i] 位置的和；这样 i 位置之前的前缀和都被统计在 hash 表中，而 i 位置后面的前缀和不需要。

代码实现

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        unordered_map<int,int> hash;
        hash[0] = 1;
        int sum = 0, ret = 0;
        for(int i = 0; i < n; i++) {
            sum += nums[i];
            if(hash.count(sum - k)) ret += hash[sum - k];
            hash[sum]++;
        }
        return ret;
    }
};