LeetCode : 560. Subarray Sum Equals K

[congr]

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

[congr]

AC, O(N^2)

class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                if (sum == k) count++;
            }
        }

        return count;
    }
}

[congr]

O(N)

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap();
        map.put(0, 1); // !!!

        int cnt = 0;
        int sum = 0;
        for (int n : nums) {
            sum += n;
            if (map.containsKey(sum - k)) cnt += map.get(sum - k);
            map.merge(sum, 1, Integer::sum);
        }

        return cnt;
    }
}