前缀和

本人没有算法基础，以下均为春招刷Leetcode的笔记，仅用于记录，侵权勿喷

前缀和本质是一种预积分手段，运行时只需要得到边界值，就能快速、无损地获得区间积分值，二维的前缀和SAT在图形学中也有重要的运用

注意数组越界，尤其是前缀乘
明确索引的含义，这关系着数组的长度是否需要+1
前缀和可以使用哈希表加速查找

除自身以外数组的乘积

给你一个整数数组 nums，返回数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。

请不要使用除法，且在 O(n) 时间复杂度内完成此题。

特点

使用左右两个前缀和

思路

最简单的方法自然是求所有数的总乘积，ans[i] = total / nums[i]，不过这道题让我们不要用除法（如果数中有0，这种做法也是错的）

我们从左做一次前缀乘，left[i]表示以0~i的前缀乘，从右开始做一次前缀乘，right[i]表示以i~n-1的前缀乘
ans[i]将数组切分为三个部分，他自己，左边和右边，左边等于0~i-1的总乘积，右边等于i+1～n-1的总乘积，左右相乘即可得到最终结果
对于边界做特殊处理

实现

vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> left(n);
        left[0] = nums[0];
        vector<int> right(n);
        right[n-1] = nums[n-1];
    	// 求左右前缀和
        for(int i = 1; i < n; ++i){
            left[i] = left[i-1] * nums[i];
            right[n-i-1] = right[n-i] * nums[n-i-1];
        }
        vector<int> ans(n);
    	// 边界处理
        ans[0] = right[1];
        ans[n-1] = left[n-2];
        for(int i = 1; i < n-1; ++i){
            ans[i] = left[i-1] * right[i+1];
        }
        return ans;
    }

和为k的子数组

leetcode

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数

-1000 <= nums[i] <= 1000

特点

数组有正有负，因此前缀和不递增

思路

固定右端点，向左找左端点，若存在和为k的连续子数组，我们能找到一个左端点，使得左右端点前缀和之差为k

由于数组中包含负数，因此左端点可能有多个

于是问题转化为从右端点出发，寻找值为ps[j] - k的左端点

当遍历完i后，当前右端点preSum[i]未来也可能是左端点，于是加入哈希表中

实现

int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> preSum(n+1, 0);
        unordered_map<int, int> mp;	// value：key出现过的次数
        mp[0] = 1;
        for(int i = 0; i < n; ++i){
            preSum[i+1] = preSum[i] + nums[i];
        }
        int ans = 0;
        for(int i = 1; i <= n; ++i){
            ans += mp[preSum[i]-k];
            ++mp[preSum[i]];	// 在遍历完i之前，我们还没遇到过i
        }
        return ans;
    }

算法：前缀和

前缀和

除自身以外数组的乘积

特点

思路

实现

和为k的子数组

特点

思路

实现