Find a subarray with a given sum.

The simple solution is to recognize all subarrays one by one and to check each subarray’s sum. The quick solution follows the following program.

Algorithm:

  • From beginning to end, traverse the array.
  • For each index in the internal loop update number = sum + array[s]
  • If the sum is equal to the sum given, then the subarray is printed out.

Output:

Find a subarray with a given sum.

Effective approach: If all of the elements in the collection are positive, then there is a concept. There is no probability that adding elements to the current subarray would be x (given sum) if a subarray has a number greater than the given sum. The aim is to use an approach similar to a sliding window. Start by adding elements to the subarray with an empty subarray until the sum is less than x. If the sum is higher than x, delete elements from the current subarray startup.

Algorithm:

Construct three variables, s=0, sum = 0

From beginning to end traverse the array.

Change the variable sum by adding current element, sum = sum + array[s]

Change the value of the variable as value = sum-array[s], and update s as, s++ if the sum is larger than the sum.

Output:

Find a subarray with a given sum.

Pin It on Pinterest

Share This