我爱学算法之—— 前缀和（中）

一、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;
    }
};