Tuesday, June 4, 2024

 Subarray Sum equals K 

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 

Constraints: 

1 <= nums.length <= 2 * 104 

-1000 <= nums[i] <= 1000 

-107 <= k <= 107 

 

class Solution { 

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

        if (nums == null || nums.length == 0) return -1; 

        int[] sums = new int[nums.length];    

        int sum = 0; 

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

            sum += nums[i]; 

            sums[i] = sum; 

        } 

        int count = 0; 

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

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

                int current = nums[i] + (sums[j] - sums[i]); 

                if (current == k){ 

                    count += 1; 

                } 

            } 

        } 

        return count; 

    } 

 

[1,3], k=1 => 1 

[1,3], k=3 => 1 

[1,3], k=4 => 1 

[2,2], k=4 => 1 

[2,2], k=2 => 2 

[2,0,2], k=2 => 4 

[0,0,1], k=1=> 3 

[0,1,0], k=1=> 2 

[0,1,1], k=1=> 3 

[1,0,0], k=1=> 3 

[1,0,1], k=1=> 4 

[1,1,0], k=1=> 2 

[1,1,1], k=1=> 3 

[-1,0,1], k=0 => 2 

[-1,1,0], k=0 => 3 

[1,0,-1], k=0 => 2 

[1,-1,0], k=0 => 3 

[0,-1,1], k=0 => 3 

[0,1,-1], k=0 => 3 

 

 

 



No comments:

Post a Comment