Subarray Sum Equals K Leetcode

 Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,1,1], k = 2

Output: 2

Example 2:

Input: nums = [1,2,3], k = 3

Output: 2

 

Code : T.c o(n^2)

class Solution {

    public int subarraySum(int[] nums, int k) {

       

        // Variable to store the number of subarrays whose sum equals k

        int count = 0;

        // Loop through each starting point of the subarray

        for (int i = 0; i < nums.length; i++) {

            // Initialize prefix sum for this subarray starting at index i

            int prefixsum = 0;

            // Loop through each ending point of the subarray starting from i

            for (int j = i; j < nums.length; j++) {

                // Add current element to the prefix sum

                prefixsum += nums[j];

                // Check if the current subarray sum equals k

                if (prefixsum == k) {

                    count++; // If yes, increase the count

                }

            }

        }

        // Return the total number of subarrays found

        return count;

    }

}

2nd Approach :0(n)

import java.util.HashMap;

class Solution {

    public int subarraySum(int[] nums, int k) {

        // Map to store prefixSum and how many times it has occurred

        HashMap<Integer, Integer> map = new HashMap<>();

       

        // Initialize with 0 sum having one occurrence

        map.put(0, 1);

        int prefixSum = 0;

        int count = 0;

        for (int num : nums) {

            // Update running prefix sum

            prefixSum += num;

            // Check if there is a prefixSum that, when subtracted from current, gives k

            if (map.containsKey(prefixSum - k)) {

                count += map.get(prefixSum - k);

            }

            // Add current prefixSum to the map (or update frequency)

            map.put(prefixSum, map.getOrDefault(prefixSum, 0) + 1);

        }

        return count;

    }

}