leetcode 560. Subarray Sum Equals K 动态规划DP子数组求和

桃扇骨 2022-06-03 04:15 203阅读 0赞

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:  
Input:nums = \[1,1,1\], k = 2  
Output: 2  
Note:  
The length of the array is in range \[1, 20,000\].  
The range of numbers in the array is \[-1000, 1000\] and the range of the integer k is \[-1e7, 1e7\].

本题题意很简单，直接使用DP动态规矩求和即可

建议和[leetcode 152. Maximum Product Subarray 最大连乘子序列 + DP动态规划][leetcode 152. Maximum Product Subarray _ _ DP] 和 [leetcode 713. Subarray Product Less Than K 移动窗口][leetcode 713. Subarray Product Less Than K] 一起学习

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    
    using namespace std;
    
    
    class Solution 
    {
    public:
        int subarraySum(vector<int>& nums, int k) 
        {
            vector<long long> dp(nums.size()+1,0);
            for (int i = 1; i <= nums.size(); i++)
                dp[i] = nums[i - 1] + dp[i - 1];
    
            int count = 0;
            for (int i = 1; i <= nums.size(); i++)
            {
                for (int j = 0; j < i; j++)
                {
                    if (dp[i] - dp[j] == k)
                        count++;
                }
            }
            return count;
        }
    };

[leetcode 152. Maximum Product Subarray _ _ DP]: http://blog.csdn.net/jackzhang_123/article/details/78016128
[leetcode 713. Subarray Product Less Than K]: http://blog.csdn.net/jackzhang_123/article/details/78884677