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

Solution:

Time: O(n^2)

class Solution {
public int subarraySum(int[] nums, int k) {
int n = nums.length;
for (int i = 1; i < n; i ++) {
nums[i] = nums[i - 1] + nums[i];
}
int count = 0;
for (int j = 0; j < n; j ++) {
for (int i = -1; i < j; i ++) {
int iVal = i == -1 ? 0 : nums[i];
if (nums[j] - iVal == k) {
count ++;
}
}
}
return count;
}
}

Time: O(n)

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