和为K的子数组

问题描述

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

子数组是数组中元素的连续非空序列。

示例 1：

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

示例 2：

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

提示：

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

解题思路

子数组是数组中元素的连续非空序列，计算连续数组单元很容易想到前缀和数组，计算前缀和数组需要O(n)的开销，可以避免两重循环下的和运算，将O(n^3)复杂度降到O(n^2)，已经可以accept。
优化则需要考虑到使用额外的数据结构对前缀和数组的值进行存储，减少对前缀和数组的遍历消耗，则可以想到哈希表。
- 假设i < j，prefix[j] - prefix[i - 1] == k，可以看到，prefix[i - 1] 的值为 prefix[j] - k，只需要在遍历i时，将prefix[i - 1]的值存入哈希表，则当遍历到j时，只需要在哈希表中查找prefix[j] - k的值即可。
- 注意的是，hash_map[0] == 1，即当prefix[j] == k 时，全选也是一种方案

Code

前缀和

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<long> prefix(n + 1 , 0);
        for(int i = 1 ; i <= n ; ++i)
            prefix[i] = prefix[i - 1] + nums[i - 1];
        int ans = 0;
        for(int i = 1 ; i <= n ; ++i)
            for(int j = i ; j <=n ; ++j)
                if(prefix[j] - prefix[i - 1] == k)
                    ans += 1;
        return ans;
    }
};

前缀和 && 哈希表

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

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。