LeetCode - 和为K的子数组

LCR 010. 和为 K 的子数组

看到这道题的时候，感觉还挺简单的，找到数组中和为k的连续子数组的个数，无非就是一个区间减去另一个区间的和等于k，然后想到了用前缀和来解决这道问题。再算连续子数组出现的个数的时候，可以使用暴力枚举，将个数全部算出来。然后在暴力枚举的基础上进行优化

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

        for (int i = 1; i <= n; i++)
        {
            for (int j = i; j <= n; j++)
            {
                if (lnum[j] - lnum[i - 1] == k)
                {
                    ans++;
                }
            }
        }

        return ans;

    }
};

代码优化，如何对这个代码进行优化？最开始我想到了双指针，如果都是正数，前缀和数组保证严格单调递增，第二层for循环可以只要可以判断成功一次即可，但是题目中给的范围是存在负数和0的，所以双指针是不行的。

换一种思路，对公式下手

假设前缀和数组为pre
pre[r] - pre[l - 1] = k;
pre[l - 1] = pre[r] - k;
写到这里，我们只需要找到有多少个前缀和是pre[r] - k即可。既然涉及到统计次数，那么就可以使用
哈希。所以对于两层for循环，考虑使用哈希进行优化。

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

        unordered_map<int,int> hash;
        hash[0] = 1; // 第0个位置也要算上，防止出现nums中第一个数字单独构成子数组
        for (int i = 1; i <= n; i++)
        {
            if (hash.find(lnum[i] - k) != hash.end()) // 如果在hash中找不到pre[r] - k
            {
                ans += hash[lnum[i] - k];// 找到有多少个前缀和是pre[r] - k,让ans加上即可
            }
            hash[lnum[i]]++;
        }

        return ans;

    }
};