个人技术分享

一 子串基础

二 和位K的子数组

1 题目

2 解题思路

前缀和+哈希（两数之和）

• 假如存在区间[left,right]，使得在[left,right]这个区间的子数组的和为k。换句话说，就是前right项和减去前left-1项和等于k，即前left-1项和等于前right项和减去k。

• 可以这样做，在扫描数组的同时，假设当前扫到第i位，记录它的前i项和sum，用该和减去k，即sum-k，判断sum-k是否为某个位置的前n项和，若是，更新统计量。

3 code

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int sum=0,ans=0;
        unordered_map<int,int>mp;
        mp[0]=1;

        for(int i:nums)
        {
            //前缀和
            sum+=i;
            //哈希
            if(mp.find(sum-k)!=mp.end()) ans+=mp[sum-k];
            mp[sum]++;
        }
        return ans;
    }
};