前缀和算法(类似于动态规划算法)

文章标题

• 前缀和介绍
• 题目：
• • 寻找数组的中心下标
  • 从自身以外数组的乘积
  • 和为K的子数组

前缀和介绍

前缀和：在一些特定的题里面，要先把一段连续的数的和先算出来，用数组来接收，然后利用这个数组
返回题目需要的答案
干讲无力 题目解释更好 请往下看

题目：

寻找数组的中心下标

题目:题目链接

题目解析:

在数组中找到一个下标，划分为2个区间 左区间的和=右区间的和,如果没有这个下标则返回-1

题目解答:

因为我们是要找到这个下标 所以我们定义两个dp表(前缀和中的dp表不一定是真正的动规)
一个dp表从左往右相加，一个dp表从右往左相加
然后循环一次 2个dp表 比较 如果 i位置的值 2个dp表相等 那么就那个 位置
细节
因为我们循环的时候
一个是从dp表的左向右 那么 第一个dp表 就要从1开始遍历数组
第二个是从右向左 那么就要 n-2位置开始插入(n是题目给的数组长度)

代码:

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

从自身以外数组的乘积

题目:题目链接

题目解析:

返回一个数组，数组中存储的是传过来的数组中 除了这个位置的乘积

题目解答:

因为是要计算除了当前位置的积，我们可以创立一个dp表从前往后遍历相乘，然后在除于当前位置的值，
但是因为有可能传过来的数组中有零 导致，出错，所以我们定义2个dp表
一个dp1表从前往后相乘
一个dp2表从后往前相乘
然后再让dp1中的i-1位置乘dp2中i位置 然后在 / i位置原数组的值
因为我们使用dp表的时候是需要多一个格子来存储一个1（方便存储）
这就避免了 途中有零出错的情况

这个图的第一个没有开辟多一个格子，自己脑补一下。。

代码:

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums)
{
    int n = nums.size();
    vector<int> dp1(n + 1);
    vector<int> dp2(n + 1);
    vector<int> sum;
    dp1[0] = 1;
    dp2[n] = 1;
    for (int i = 1; i <= n; i++)
    {
        dp1[i] = dp1[i - 1] * nums[i-1];
    }
    for (int i = n-1; i >= 0; i--)
    {
        dp2[i] = dp2[i + 1] * nums[i];
    }
    for (int i = 1; i <= n; i++)
    {
        sum.push_back((dp1[i - 1] * dp2[i]));
    }
    return sum;

}
};

和为K的子数组

题目:题目链接

题目解析:

找到一个连续的子数组中的和等于K，返回个数

题目解答:

因为是找到子数组，所有我们可以用前缀和来统计出现的和为多少
找到一次之后再前缀和数组的值减去前缀和数组中最前面的值
判断他是否大于k 如果大于k再减 减到小于k 然后在往后进行前缀和
因为一个前缀和来统计的话 还要依次遍历 所以时间复杂度还不如暴力枚举
所以我们需要借助一个哈希表来存储
哈希表中的key值存的是 前缀和
如果判断当前哈希表中没有这个前缀和那么会插入并且要让他的值为1
细节：因为如果哈希表中 是要找到k这个值的数组 那么我们要在hash[0]=1
因为如果不初始化的话 那么第一次统计有多少个的时候 会统计成0个
定义一个变量x来存储前缀和
一个变量ret 统计个数
代码可能解释会更好一点

代码:

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(auto x:nums)
        {
            sum+=x;
            if(hash.count(sum-k))//count()括号中 如果sum-k这个位置
            //在hash中值不为0那么就让ret+=上这个位置的值  那么为真 其他为假
            //例如
            //{0,1};
            //{1,1};
            //{2,1};
            //{3,1};
            //这里sum=3的时候-k 会探查hash[1]位置的值
            //如果为真那么 +=他里面的值
            //下面也是
            //{4,1};这里会找[2]
            //{5,1};[3]
            //{6,1};[4]
            //按照上述操作 就可以找到所有的子数组
            //上述操作可以进行让前缀和减去前面的直到小于k，然后在往后遍历
            {
                ret+=hash[sum-k];
            }
            hash[sum]++;
        }
        return ret;
    }
};