首页 > 代码库 > 560. Subarray Sum Equals K

560. Subarray Sum Equals K

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

示例:

Input: nums = [1,1,1], k = 2
Output: 2

Note:

  1. The length of the array is in range [1, 20,000].
  2. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

 

题解:

  看着题目的注意事项就知道,这道题不能用枚举法来解决(数组长度最大20000,枚举的话复杂度至少为O(n^2),根本不可能)。通过类似于动态规划问题中的“最长连续子序列问题”来求解,也存在问题:因为不可能开出20000*20000的二维数组,这也是本题的难度所在。但是,因为本题的约束条件是“连续”,于是有了这样的一个性质:假设s(i,j)为子数组nums[i,j]之间的和,sum(k)为子数组nums[0...k]之间的和,那么有:s(i,j) = sum(j) - sum(k)

     基于上面的性质,可以得出这样的一个技巧,用m[currsum]来记录下“对于任意的j>=0 且 j <n,sum(j) = currsum的j的个数”,也就是说,一端下标为0,另一端下标为j的子数组,加起来等于currsum的子数组有多少个。有了这样的一个计数,答案就很容易计算出来了。我们先从nums[0]开始,对数组进行累加,假设当前的累加结果为sum(i),则m[sum(i) - k]就意味着,一端下标为0,另一端下标为j加起来等于sum(i) - k的子数组有多少个,也就意味着,一端为j,另一端为i,这段总和为k的子数组有多少个!将所有这样的子数组的个数加起来,就可以得到答案。

 

代码:

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int sum = 0 ;
        int n = nums.size();
        map<int,int> m; //sum->num of subrrays
        int res = 0;
        
        for(int i = 0; i < n ; i ++)
        {
            m[sum] ++;
            sum += nums[i];
            res += m[sum-k];
        }
        
        return res;
    }
};

 

560. Subarray Sum Equals K