Given an array that could contain negative and positive integers, find a subarray that sums up a given sum. An efficient solution to this problem employs hash maps, which can be abstracted using a dictionary in Python, as shown below.
The code snippet below provides an algorithm that uses a hash map to find a subarray with the given sum.
Note: To run the following code, provide input for the array in the form of just integers separated with a space (without commas or brackets).
For example, enter [-3, 5, 1, -6, 4] as:
def subarray_finder(arr, sum):hash_map = dict()current_sum = 0for i in range(len(arr)):current_sum += arr[i]if current_sum == sum:subarray = arr[:i+1]return subarrayprevious_sum = current_sum - sumif previous_sum in hash_map:start_index = hash_map[previous_sum]+1subarray = arr[start_index: i+1]return subarrayhash_map[current_sum] = ireturn "No subarray found"sum = 6 #change the value of sumarr = input().split()arr = [int(i) for i in arr]subarray = subarray_finder(arr, sum)print(subarray)
Enter the input below
The algorithm operates with the following properties:
Lines 1–24: These lines contain the function subarray_finder
that takes the original array, arr
, and the given sum sum
, and finds the subarray if it exists.
Line 3: An empty dictionary is created and stored in hash_map
, which abstracts our hash map.
The keys of the dictionary contain the sum of the array's elements from index 0 to an index k
.
The values of the keys will be k
.
Line 5: The variable current_sum
stores the sum of the array's elements from index 0 to another index (this will be used when traversing the array).
Lines 7–22: A single traversal of the array is performed:
Line 9: current_sum
is incremented to store the sum of the array from index 0 to index i
.
Lines 11–13: If a subarray is found that begins at index 0 and ends at index i
, then it's returned.
Line 15: The variable previous_sum
stores the sum of the array's elements from index 0 to index k
. It also acts as the key to hash_map
.
Lines 17–20: The previous_sum
tells us about the starting index of the subarray (which is referred to as the index k
above). Therefore, if previous_sum
exists in hash_map
, index k
will be the value corresponding to the previous_sum
key. Elements from index k
up until index i
are returned since they sum up to the given sum.
Line 22: If a subarray is not found that ends at the index i
, a key-value pair is added in hash_map
which stores the total of the array until the index i
.
Line 24: We are informed if a subarray isn't found at the end of the traversal.
Line 27: We can change the given sum, and it's stored in sum
.
Lines 29 and 30: These take our input for the array.
Lines 32 and 33: The subarray is found by calling the subarray_finder
function, and is then printed.