[数据结构与算法]数据结构 前缀与积分图 560. Subarray Sum Equals K (Medium)

直接写超时了

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

其实没必要写那个vector

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

如果像上面这样写就是On2，转变思路，求一个区间和为k，就是right的前缀和减left的前缀和是k，在遍历过程中，我们用哈希表统计每个不同的前缀和出现的次数，当遍历到i时，统计psum-k出现的次数，就是i这个位置跟前面所能构成的和为k的区间

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        int count = 0, psum = 0;
        unordered_map<int, int> map;
        map[0] = 1;//注意数组一个数都没有的时候，也有一个psum是0
        for(int i = 0; i < n; i++){
            psum += nums[i];
            count += map[psum-k];
            map[psum]++;
        }
        return count;
    }
};