560. Subarray Sum Equals K [Medium]

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

Constraints:

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

---

算法思路：

方法1：使用range sum方法，蕴含dp思想

测试案例非常差劲，自己举一个

Input:  nums = [1,2,2,-2,2,-2,1] ,  k = 4

[1,2,2,-2,2,-2,1] 

[1,3,5,3,5,3,4]     -->    range sum

[1,3,5,3,5,3,4]     -->    [1,2,2,-2,2,-2,1]     -->    5 - 1 = 4

[1,3,5,3,5,3,4]     -->    [1,2,2,-2,2,-2,1]     -->    5 - 1 = 4

[1,3,5,3,5,3,4]     -->    [1,2,2,-2,2,-2,1]     -->    4 - 0 = 4

Output:  3

// O(n^2) // TLE: 80 / 81 test cases passed. class Solution { public: int subarraySum(vector<int>& nums, int k) { int n = nums.size(); vector<int> sum(n, 0); sum[0] = nums[0]; for (int i = 1; i < n; i++) sum[i] = sum[i - 1] + nums[i]; int res = 0; for (int i = 0; i < n; i++) { if (sum[i] == k) res++; for (int j = i + 1; j < n; j++) { if (sum[j] - sum[i] == k) res++; } } return res; } };

方法2：使用hash map改进一下，但是计算的时候，当前位置只能使用该位置前面的sum和，因此无法开始一下子都放入unoredred_map中，所以便计算边放入。方法2相对于方法1，是从当前位置不断向前扩展并使用hash map优化了一下。

// O(n) class Solution { public: int subarraySum(vector<int>& nums, int k) { int n = nums.size(); unordered_map<int, int> um; um[0] = 1; int subSum = 0; int res = 0; for (int i = 0; i < n; i++) { subSum += nums[i]; if (um.find(subSum - k) != um.end()) { res += um[subSum - k]; } um[subSum]++; } return res; } };