560. 和为K的连续子数组

· 约 1 分钟阅读 · – 次阅读 leetcode
#array

560. 和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

 

示例 1：

输入：nums = [1,1,1], k = 2 输出：2 示例 2：

输入：nums = [1,2,3], k = 3 输出：2  

提示：

1 <= nums.length <= 2 * 104 -1000 <= nums[i] <= 1000 -107 <= k <= 107

暴力枚举， 无法通过OJ

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size(), ans = 0;
        for (int start = 0; start < n; start++) {
            int tmp = 0;
            for (int end = start; end < n; end++) {
                tmp += nums[end];
                if (tmp == k) ans++;
            }
        }
        return ans;

    }
};

前缀和+哈希表

记录pre[i]为序号为0-i的数组中所有数的和。 对于序号为[i, j]的子树组来说，如果pre[j]-pre[i-1] == k, 则其为一个目标答案。

可以考虑用一个哈希表记录所有前缀和出现的次数，遍历一次即可求得答案。

时间复杂度和空间复杂度均为O(n)

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size(), ans = 0, pre = 0;
        unordered_map<int, int> mp;
        mp[0] = 1;
        for (int start = 0; start < n; start++) {
            pre += nums[start];
            if (mp.find(pre-k) != mp.end()) {
                ans += mp[pre-k];
            }
            mp[pre]++;
        }
        return ans;

    }
};