Java Solution, PreSum + HashMap


  • 61

    Solution 1. Brute force. We just need two loops (i, j) and test if SUM[i, j] = k. Time complexity O(n^2), Space complexity O(1). I bet this solution will TLE.

    Solution 2. From solution 1, we know the key to solve this problem is SUM[i, j]. So if we know SUM[0, i - 1] and SUM[0, j], then we can easily get SUM[i, j]. To achieve this, we just need to go through the array, calculate the current sum and save number of all seen PreSum to a HashMap. Time complexity O(n), Space complexity O(n).

    public class Solution {
        public int subarraySum(int[] nums, int k) {
            int sum = 0, result = 0;
            Map<Integer, Integer> preSum = new HashMap<>();
            preSum.put(0, 1);
            
            for (int i = 0; i < nums.length; i++) {
                sum += nums[i];
                if (preSum.containsKey(sum - k)) {
                    result += preSum.get(sum - k);
                }
                preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);
            }
            
            return result;
        }
    }
    

  • 11
    H

    @shawngao

    Very elegant answer. Thank you for sharing. The if block can also be removed. :)

    public class Solution {
        public int subarraySum(int[] nums, int k) {
            int sum = 0, result = 0;
            Map<Integer, Integer> preSum = new HashMap<>();
            preSum.put(0, 1);
            
            for (int num : nums) {
                sum += num;
                result += preSum.getOrDefault(sum - k, 0);
                preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);
            }   
            return result;
        }
    } 
    

  • 0
    S

    Python version.

    class Solution(object):
        def subarraySum(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: int
            """
            d = {0: 1}
            n = 0
            s = 0
            for i in range(len(nums)):
                s += nums[i]
                n += d.get(s - k, 0)
                d[s] = d.get(s, 0) + 1
            return n

  • 1
    W

    You can use the build-in merge method.

    public int subarraySum(int[] nums, int k) {
      int res = 0, sum = 0, l = nums.length;
      Map<Integer, Integer> map = new HashMap<>();
      map.put(0, 1);
      for (int i = 0; i < l; res += map.getOrDefault((sum += nums[i++]) - k, 0), map.merge(sum, 1, Integer::sum));
      return res;
    }

  • 0
    L
    This post is deleted!

  • 0

    No, the PreSum doesn't get TLE for now, and it's indeed very slow. :)


  • 1
    I

    No need to put(0, 1) this way.

            int ans = 0, sum = 0;
            Map<Integer, Integer> map = new HashMap<>();
            for (int num : nums) {
                map.put(-sum, map.getOrDefault(-sum, 0) + 1);
                sum += num;
                ans += map.getOrDefault(k - sum, 0);
            }
            return ans;
    

  • 0
    A

    why sum-k?


  • 0
    I
    This post is deleted!

  • 3
    E

    @apt275 sum - k means the array elements in between add up to k


  • 0
    F

    Why I change the order of put and if, the code will be wrong? Since the case of k = 0?


  • 0

    @shawngao Two qq

    • In what way does it check if the subarray is continuous?
    • You say, "from solution 1" - how could you deduce solution 2 from solution 1? I mean to ask, how do we get SUM[i,j] if we know SUM[0,i-1] and SUM[0,j]?

  • 0

    @shawngao You store the sum and the number of times you encountered this sum (by doing preSum.getOrDefault(sum, 0) + 1) in a map - could you kindly explain why? How is the number of times useful here...


  • 1
    P

    @BatCoder
    the frequency is needed here because you need to add that to the result. Each time you find a sum that the hash map contains
    (sum - k), this means (sum - k) is a PreSum for a array some previous elements, and there could be more than one of them, so use result += preSum.get(sum - k) instead of result++.


  • 0

    @pumpkin3
    Thank you. I got it somewhat. Could you kindly explain the entire code please?


  • 4
    P

    @BatCoder
    sum is the presum for first i+1 numbers in the array, for example, sum of first 1 number is nums[0].
    preSum.put(0,1); because the sum of first 0 number is 0 and this is an empty array[], which is also a subarray for nums. In other words, the number of time sum = 0 exists is 1.
    then we loop through the array, calculate the presum for first i+1 number and check if the map contains key (sum - k) , if it is, we increase the result by the number of (sum - k) we get from hash map.
    We also need to put all sum in the map, that's what this line of code does: preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);


  • 1

    @pumpkin3 said in Java Solution, PreSum + HashMap:

    We also need to put all sum in the map, that's what this line of code does: preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);

    @pumpkin3
    Okay, so I got your point. We are storing <sum, frequency of this sum> in the map. Then we navigate through the input array, calculating the sum and checking if its complement (sum-k) exists in the map. If it does, then we simply update the counter variable (result); if not, then we capture this sum and its frequency in the map. Is my understanding correct?

    And one qq - we check for the complement sum-k in the map, so doesn't it make sense to store the complement (rather than the sum) in the map?


  • 5
    P

    @BatCoder
    yes you understand it almost correctly.
    One thing to know is that no matter the complement (sum - k) exits or not, we always need to increase the frequency of the sum in the map.

    As for your question, we need to find the number of subarrays that whose sum equals k. To compute the sum of an subarray, it is useful to use preSum. For example, given an arraynums = [-3, 1, 2, -3, 5], its preSum is preSum = [0, -3, -2, 0, -3, 2]. Let's say we want to calculate the sum of subarray nums[1,3] which is [1, 2, -3], it can be computed using preSum:
    preSum[4] - preSum[1] = -3 - (-3) = 0.
    If a subarray from i to j whose sum is k, it means preSum[j+1] - preSum[i] = k. So the complement (sum - k) equals another sum.


  • 0

    @pumpkin3 Nice explanation. Thank you! :)


  • 4

    Same idea..btw, brute force works fine this time.

        public int subarraySum(int[] nums, int k) {
            int[] preSum = new int[nums.length];
            preSum[0] = nums[0];
            for (int i = 1; i < nums.length; i++) preSum[i] = preSum[i - 1] + nums[i];
            int result = 0;
            for (int i = 0; i < preSum.length; i++) {
                if (preSum[i] == k) result++;
                for (int j = i + 1; j < preSum.length; j++) {
                    if (preSum[j] - preSum[i] == k) result++;
                }
            }
            return result;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.