Formatted question description: https://leetcode.ca/all/560.html
560. Subarray Sum Equals K
Level
Medium
Description
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:
- 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].
Solution
Use a map to store each sum and the count of subarrays of the sum. Put sum 0 with count 1 to the map initially.
Loop over nums
and calculate the total sum sum
. For each num
in nums
, add num
to sum
, and obtain the count of subarrays with sum sum - k
. Add the sum to the result. Then update the map with the count of subarrays with sum sum
. Finally, return the result.
-
public class Subarray_Sum_Equals_K { public static void main(String[] args) { Subarray_Sum_Equals_K out = new Subarray_Sum_Equals_K(); Solution s = out.new Solution(); System.out.println(s.subarraySum(new int[]{1, 1, 1}, 2)); } // time: O(N) // space: O(N) // https://leetcode.com/problems/subarray-sum-equals-k/solution/ class Solution_hashmap { public int subarraySum(int[] nums, int k) { // sum => count of to-this-sum HashMap <Integer, Integer> hm = new HashMap<>(); hm.put(0, 1); int count = 0; int sum = 0; for (int i = 0; i < nums.length; i++) { sum += nums[i]; if (hm.containsKey(sum - k)) { // same idea as, if (sum[end] - sum[start] == k) { count += hm.get(sum - k); } hm.put(sum, hm.getOrDefault(sum, 0) + 1); } return count; } } // time: O(N^2) // space: O(1) class Solution_withNoExtraSpace { public int subarraySum(int[] nums, int k) { int count = 0; for (int start = 0; start < nums.length; start++) { int sum = 0; // @note: sum for each start point for (int end = start; end < nums.length; end++) { sum += nums[end]; if (sum == k) count++; } } return count; } } // time: O(N^2) // space: O(N) class Solution2 { public int subarraySum(int[] nums, int k) { int count = 0; // sum value from 1 to i-th element int[] sum = new int[nums.length + 1]; sum[0] = 0; // cached sum for (int i = 1; i <= nums.length; i++) { sum[i] = sum[i - 1] + nums[i - 1]; } for (int start = 0; start < nums.length; start++) { for (int end = start + 1; end <= nums.length; end++) { if (sum[end] - sum[start] == k) { count++; } } } return count; } } // brute force class Solution { int count = 0; public int subarraySum(int[] nums, int k) { for (int start = 0; start < nums.length; start++) { for (int end = start + 1; end <= nums.length; end++) { int sum = 0; for (int i = start; i < end; i++) { sum += nums[i]; } if (sum == k) count++; } } return count; } } }
-
// OJ: https://leetcode.com/problems/subarray-sum-equals-k/ // Time: O(N) // Space: O(N) class Solution { public: int subarraySum(vector<int>& nums, int k) { int ans = 0, sum = 0; unordered_map<int, int> m{ {0, 1} }; for (int n : nums) { sum += n; auto it = m.find(sum - k); if (it != m.end()) ans += it->second; m[sum]++; } return ans; } };
-
class Solution(object): def subarraySum(self, nums, k): """ :type nums: List[int] :type k: int :rtype: int """ preSum = ans = 0 visit = {0: 1} for i, n in enumerate(nums): preSum += n ans += visit.get(preSum - k, 0) visit[preSum] = visit.get(preSum, 0) + 1 return ans
Java
-
class Solution { public int subarraySum(int[] nums, int k) { Map<Integer, Integer> map = new HashMap<Integer, Integer>(); map.put(0, 1); int count = 0; int sum = 0; int length = nums.length; for (int i = 0; i < length; i++) { sum += nums[i]; int curCount = map.getOrDefault(sum - k, 0); count += curCount; int sumCount = map.getOrDefault(sum, 0); map.put(sum, sumCount + 1); } return count; } }
-
// OJ: https://leetcode.com/problems/subarray-sum-equals-k/ // Time: O(N) // Space: O(N) class Solution { public: int subarraySum(vector<int>& nums, int k) { int ans = 0, sum = 0; unordered_map<int, int> m{ {0, 1} }; for (int n : nums) { sum += n; auto it = m.find(sum - k); if (it != m.end()) ans += it->second; m[sum]++; } return ans; } };
-
class Solution(object): def subarraySum(self, nums, k): """ :type nums: List[int] :type k: int :rtype: int """ preSum = ans = 0 visit = {0: 1} for i, n in enumerate(nums): preSum += n ans += visit.get(preSum - k, 0) visit[preSum] = visit.get(preSum, 0) + 1 return ans