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:

  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].

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
    
    

All Problems

All Solutions