前缀和算法(类似于动态规划算法)-Toy模板网

这篇具有很好参考价值的文章主要介绍了前缀和算法(类似于动态规划算法)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前缀和介绍

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

题目：

寻找数组的中心下标

题目:题目链接
前缀和算法(类似于动态规划算法),算法,算法,动态规划,c++,stl,leetcode,哈希算法
题目解析:

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

题目解答:

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

代码:文章来源地址https://www.toymoban.com/news/detail-766245.html

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

从自身以外数组的乘积

题目:题目链接
前缀和算法(类似于动态规划算法),算法,算法,动态规划,c++,stl,leetcode,哈希算法
题目解析:

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

题目解答:

因为是要计算除了当前位置的积，我们可以创立一个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的子数组

题目:题目链接
前缀和算法(类似于动态规划算法),算法,算法,动态规划,c++,stl,leetcode,哈希算法
题目解析:

找到一个连续的子数组中的和等于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;
    }
};