{"id":799,"date":"2023-12-07T17:00:00","date_gmt":"2023-12-07T17:00:00","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=799"},"modified":"2023-12-08T13:05:21","modified_gmt":"2023-12-08T13:05:21","slug":"subarray-sum-equals-k","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/subarray-sum-equals-k\/","title":{"rendered":"Subarray Sum Equals K (C++, Java, Python)"},"content":{"rendered":"\n

Arrays play a significant role in the world of programming and there are a lot of interview questions that depend on array data structure. In this article, we will explore different approaches to solving the ‘subarray sum equals k’ problem, starting with the brute force approach and gradually moving towards more efficient solutions using techniques of prefix sums.<\/p>\n\n\n\n

What is the Subarray Sum Equals K Problem?<\/strong><\/h2>\n\n\n\n

One particular problem that frequently arises is finding subarrays whose sum equals a given number, commonly referred to as the “subarray sum equals k” problem. This problem requires several subarrays with sum k where k is the given target. <\/p>\n\n\n\n

In this problem, we are given an array and we have to tell the number of subarrays that sum equals k, a subarray is a contiguous subsequence of an array.<\/strong><\/p>\n\n\n\n

Let us understand it with an example:<\/p>\n\n\n\n

Array = [1,2,3,2,1,4]
k = 5
Output = 3<\/p>\n\n\n\n

There are 3 subarrays, i.e. {2,3}, {3,2}, {1,4} whose element\u2019s sum is 5.<\/p>\n\n\n

\n
\"Example<\/figure>\n<\/div>\n\n\n

Check out Kadane’s Algorithm<\/a> to learn how to find maximum sum subarray.<\/p>\n\n\n\n

Brute Force Approach<\/strong><\/h2>\n\n\n\n

In the naive approach, we will generate all possible subarrays and check whether the sum of elements in the array is equal to k or not.<\/p>\n\n\n\n

Steps for brute force approach:<\/p>\n\n\n\n