【算法基础】--前缀和

解析：

还是使用前缀和的思维。使用俩数组分别来记录中心下标左边的和，以及右边的和。 然后遍历整个数组，如果俩数组相等，返回下标i

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int n=nums.size();
        vector<int>f(n),g(n);

        //处理前缀和 后缀和
        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;
    }
};

例题2：

题目描述：
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。请不要使用除法，且在 O(n) 时间复杂度内完成此题。

解析：这里使用的方法和上一道题解法类似，只不过换了一种说法。题目所说求除i为之外其余元素的积，我们换一种思维就是 前缀积和后缀积的积。假设我们要求i位置的值时，我们可以求出【0,i-1】位置区间所有元素积和【i+1,n-1】区间范围所有元素积。再将他俩相乘即可。草图如下：

代码：

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n=nums.size();
        vector<int>f(n),g(n);
        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>ans(n);
        for(int i=0;i<n;i++)
        {
            ans[i]=g[i]*f[i];
        }
        return ans;
    }
};

例3：

给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的非空 子数组 的数目。子数组 是数组中 连续 的部分。

解析：

这里先讲一下有关知识点：同余定理

在c++/java中：（负%正）=负，为了让这个余数是正数，给出了这样的方法修正：a%p+p,但是又不能确定a是正数还是负数，为了统一：(a%p+p)%p,以后取模运算，有负数时，用这个方法。

在该题中，求可被k整除的子数组个数，我们用到前缀和+哈希方法。在[0,i-1]区间内找到多少前缀和余数等于(sum%k+k)%k.,余数存进哈希表。定义个哈希表，第一个int代表前缀和的余数，第二个代表个数。

代码：

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int,int>hash;//存的是余数
        hash[0%k]=1;//余数
        int sum=0,res=0;
        for(auto x:nums)
        {
            sum+=x;//算出当前位置前缀和
            int y=(sum%k+k)%k;//求余数
            if(hash.count(y))   res+=hash[y];
            hash[y]++;//不要忘记将余数继续扔进哈希表里

        }
        return res;
    }
};

希望读者喜欢
你们的支持是小编动力的源泉