Data Structure & Algorithms
  • 🖌️Unlocking the Power of Algorithms with C#
  • Data Structure
    • Data Structure
    • Big O
    • Array
    • Linked Lists
    • Stacks
    • Queues
    • Hash Tables
    • Trees
    • Graphs
    • Heap Sort
    • ParkingLot Algorithm
    • LRU cache
    • Priority Queue
  • Algorithms
    • Algorithm
    • Recursion
    • Sorting
    • Searching
    • Dynamic Programming
  • Problems
    • Array
      • Two Sum
      • Two Sum II - Input Array Is Sorted
      • Contains Duplicate
      • Maximum Subarray
      • House Robber
      • Move Zeroes
      • Rotate Array
      • Plus One
      • Find number of subarrays with even length
      • Find number of subarrays with even sum
      • Find Missing Element
      • Reduce Array Size to The Half
      • Remove Duplicates
      • Merge Sorted Arrays
      • Arrays Intersection
      • 3Sum
      • Trapping Rain Water
      • Maximum sum of a subarray
      • Longest Subarray
      • Subarray Sum Equals K
      • Container With Most Water
      • Missing Number
      • Roman to Integer
      • First Missing Positive
      • Unique Integers That Sum Up To 0
      • Integer to Roman
      • Flatten
    • String
      • Check if two strings are permutation of each other
      • String Compression
      • Palindrome Permutation
      • Determine if a string has all Unique Characters
      • One Away
      • Longest Substring Without Repeating Characters
      • Valid Palindrome
      • Valid Palindrome II
      • Backspace String Compare
      • First Unique Character in a String
      • Is Subsequence
      • URLify a given string
      • String has same characters at same position
      • Number of Ways to Split a String
      • Check whether two Strings are anagram of each other
      • Print last `n` lines of a big file or big string.
      • Multiply Strings
    • Matrix
      • Search a 2D Matrix
      • Search a 2D Matrix II
      • Rotate Matrix
      • Spiral Matrix
      • Set Matrix Zeroes
    • Bit Manipulation
      • Sum of Two Integers
      • Reverse Number
      • Reverse Number II
      • Binary Bits Count
      • Binary Bits Count II
    • Stack
      • Valid Parentheses
      • Balance or not expression
      • Decode String
    • Tree
      • Binary Tree Inorder Traversal
      • Binary Tree Preorder Traversal
      • Binary Tree Postorder Traversal
      • Binary Tree Level Order Traversal
      • Binary Tree Return All Root-To-Leaf Paths
      • Binary Tree Height-Balanced
      • Valid Binary Search Tree
      • Binary Tree Sum of all left leaves.
    • Linked List
      • Linked List Delete Middle Node
      • Merge Sorted Linked List
      • Reverse Linked List
      • Remove Duplicates from Sorted List
      • Remove Duplicates from Unsorted List
      • Linked List Cycle
    • Graph
      • The Number Of Islands
      • Number of Closed Islands
      • Max Area of Island
      • Rotting Oranges
      • Number of Provinces
      • Course Schedule
      • Surrounded Regions
      • Snakes and Ladders
      • Widest Path Without Trees
      • Knight Probability in Chessboard
      • Possible moves of knight
      • Check Knight Tour Configuration
      • Steps by Knight
      • Network Delay Time
    • Greedy
      • Best Time to Buy and Sell Stock
      • Best Time to Buy and Sell Stock II
      • Smallest Subset Array
      • Jump Game
    • Backtracking
      • Towers of Hanoi
      • Subsets
      • Combination Sum
      • Sudoku Solver
      • Word Search
    • Heap
      • Kth Largest Element in an Array
      • Top K Frequent Elements
    • Sorting
      • Order Colors String
    • Recursion
      • Number To Text
      • Divide Number
Powered by GitBook
On this page
  1. Problems
  2. Array

Subarray Sum Equals K

Array, Hash Table

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

Solutions

Approach - Brute Force Technique

Steps

  1. Initialize Counter: The algorithm starts by initializing a counter count to 0. This will keep track of the number of subarrays that sum to k.

  2. Iterate Over Array: The algorithm then enters a nested loop that iterates over each possible subarray in nums.

    • Calculate Subarray Sum: For each subarray, the algorithm calculates the sum of the elements in the subarray.

    • Check for Desired Sum: If the sum of the elements in the subarray equals k, the algorithm increments count.

  3. Return Result: After the loops, the algorithm returns count, which is the total number of continuous subarrays whose sum equals to k.

public class Solution {
    public int SubarraySum(int[] nums, int k) {
        int count = 0;
        for (int start = 0; start < nums.Length; start++) {
            int sum=0;
            for (int end = start; end < nums.Length; end++) {
                sum+=nums[end];
                if (sum == k)
                    count++;
            }
        }
        return count;
    }
}

Complexity

  • Time complexity: O(N^2)

  • Space complexity: O(1)

Approach - Hash Table Technique

Steps

  1. Initialize Variables: The algorithm starts by initializing a dictionary prefix to keep track of cumulative sums and their counts, an integer sum to keep track of the cumulative sum, and an integer ret to keep track of the number of subarrays that sum to k.

  2. Handle Base Case: The algorithm adds an entry to the prefix dictionary for a sum of zero with a count of one. This represents the sum of no elements.

  3. Iterate Over Array: The algorithm then enters a loop that iterates over each element in the input array nums.

    • Update Cumulative Sum: For each element, the algorithm adds the element’s value to sum.

    • Check for Subarray Sum: The algorithm calculates the value find as the difference between the current cumulative sum and k. If find is in the prefix dictionary, it means that there is a subarray ending at the current index with a sum of k. The algorithm increments ret by the count of find in prefix.

    • Update Prefix Dictionary: The algorithm then checks if the current cumulative sum is in the prefix dictionary. If it is, the count is incremented; otherwise, a new entry is added with a count of one.

  4. Return Result: After the loop, the algorithm returns ret, which is the total number of continuous subarrays whose sum equals to k.

public class Solution {
    public int SubarraySum(int[] nums, int k) {

        Dictionary<int, int> prefix = new Dictionary<int, int>();
        int sum = 0;
        int ret = 0;
        prefix[0] = 1; // we always have 1 sum of zero, which is sum of none.
        for (int i = 0; i < nums.Length; i++)
        {
            sum += nums[i];

            int find = sum - k;
            if (prefix.ContainsKey(find))
            {
                ret += prefix[find];
            }
            if (prefix.ContainsKey(sum))
            {
                prefix[sum]++;
               
            }
            else
            {
                
                prefix.Add(sum, 1);
            }
            
        }
        return ret; 
    }
}

Complexity

  • Time complexity: O(N)

  • Space complexity: O(N)

PreviousLongest SubarrayNextContainer With Most Water

Last updated 1 year ago