10.5 和为K的子数组

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

1、暴力解法

优化算法大部分都是对暴力解法优化而来的，所以我认为先掌握暴力解法对理解优化算法是有帮助的。这道题的暴力解法就是依次遍历，需要注意的是设置int n = nums.size()；会有效降低程序的复杂度，如果把nums.size()加入for循环则程序每次都会调用.size()。

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

2、 前缀和

思路：
假如存在区间[left,right]，使得在[left,right]这个区间的子数组的和为k。换句话说，就是前right项和减去前left-1项和等于k，即前left-1项和等于前right项和减去k。
可以这样做，在扫描数组的同时，假设当前扫到第i位，记录它的前i项和sum，用该和减去k，即sum-k，判断sum-k是否为某个位置的前n项和，若是，更新统计量。
为什么呢，因为如果sum-k为某个位置的前n项和，即该和是已知的，是数组中实际存在的，如果我们用前i项和减k等于这个已知数，那么k也就是实际存在的。

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

为什么要初始化初始化mp[0]=0呢？比如给出输入[3,-3]， k = 0.如果初始化mp[0]=0则无法得到正确答案。

unordered_map：

优点： 因为内部实现了哈希表，因此其查找速度非常的快
缺点： 哈希表的建立比较耗费时间
适用处：对于查找问题，unordered_map会更加高效一些，因此遇到查找问题，常会考虑一下用unordered_map