一道题学会如何使用哈希表

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

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

示例 1：

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

示例 2：

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

题目很简单对吧，理解题目意思就可以暴力把他做出来。

暴力做法：两层for循环

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int res=0;
        for(int i=0;i<nums.size();i++)
        {
            int temp=0;
            for(int j=i;j<nums.size();j++)
            {
                temp+=nums[j];
                if(temp==k){
                    res++;
                }
            }
        }
        return res;
    }
};

哈希表做法：首先计算一个前缀和，维护一个哈希表（unordered_map）来记录前缀和及其出现的次数。通过在迭代过程中不断更新前缀和，然后查找是否存在符合条件的前缀和（pre - k），来累加符合条件的子数组个数。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int res = 0;  // 用于存储符合条件的子数组个数
        unordered_map<int, int> mp;  // 用于存储前缀和及其出现的次数
        int pre = 0;  // 当前的前缀和

        for (int i = 0; i < nums.size(); i++) {
            mp[pre]++;  // 将当前前缀和的次数加一
            pre += nums[i];  // 更新前缀和

            // 如果存在前缀和 pre - k，说明从该位置到当前位置的子数组和为 k
            res += mp[pre - k];
        }

        return res;  // 返回符合条件的子数组个数
    }
};