560.Subarray Sum Equals K

Tags: Array Hash Table Medium

Links: https://leetcode.com/problems/subarray-sum-equals-k/

---

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

Input:nums = [1,1,1], k = 2
Output:2

Note:

1. The length of the array is in range [1, 20,000].
2. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

---

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = nums.size(); if (!n) return 0;
        unordered_map<int, vector<int>> um;
        um[nums[0]].push_back(0);
        int sum = nums[0];
        for (int i = 1; i < n; ++i) {
            sum += nums[i];
            um[sum].push_back(i);
        }


        int cnt = 0;
        if (um.find(k) != um.end()) cnt += um[k].size();
        sum = 0;
        for (int i = 0; i < n; ++i) {
            sum += nums[i];
            if (um.find(k + sum) != um.end()) {
                auto & vec = um[k + sum];
                int len = vec.size();
                for (int j = 0; j < len; ++j) {
                    if (vec[j] > i) {
                        cnt += len - j; break;
                    }
                }
            }
        }

        return cnt;
    }
};

题意就是找连续的子数组让和为k，连续子数组和很容易想到前缀和来计算区间子数组的和，可能存在的问题就是会有多个满足条件的位置，那么可以用hash Table来进行优化，让键是前缀和，值是前缀和等于键的下标，用vector来表示。很明显，数组的里的下标肯定是升序的，那么如果查找到某个位置满足，那么后面的位置就都会满足，思想很类似归并求逆序数的方法。注意的情况是考虑子数组是包含第一个元素的情况，和不包含第一个元素的子数组两种情形。

题型类似的还有LeetCode 325.