Subarray Sum Equals K

LeetCode https://leetcode.cn/problems/subarray-sum-equals-k/

class Solution {
    public int subarraySum(int[] nums, int k) {
        if (nums == null || nums.length < 1) {
            return 0;
        }
        int len = nums.length;
        // Array to store cumulative sum of elements in nums
        // from the beginning up to index i, inclusive.
        int[] prefixSum = new int[len + 1];
        prefixSum[0] = 0;
        for (int i = 0; i < len; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
        
        int count = 0;
        for (int left = 0; left < len; left++) {
            for (int right = left; right < len; right++) {
                if (prefixSum[right + 1] - prefixSum[left] == k) {
                    count++;
                }
            }
        }
        
        return count;
    }
}

Complexity

• Time = O($n^2$)
• Space = O(n)

Follow up: Time = O(n)

• 前缀和 + 哈希表优化