The question is quite simple and perhaps classic. Given an array of n numbers and target sum, find the largest sequence within the array such that the sum of the array is equal to the target sum. Design an implementation in O(n) time complexity.
Hint? Use hash map.
This is how you can solve this. Say the array is given by {a_1, a_2, a_3, ..., a_n}. Any subsequence of the array will have the form {a_i, ..., a_j} where i <= j <= n. If you let S_k be the sum from a_1 through a_k, then you notice that sum of any subsequence is given by S_j - S_i.
Thus, you need to go through each number and calculate S_j, and see if there has been S_i in the hash map such that S_j - S_i = target. If so, you can update your result.
In code, you can easily implement with Python:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import numpy as np | |
def find_max_sequence_of_target_sum(array, target): | |
hash_map = {} | |
sum2 = 0 | |
result = 0 | |
seq = [] | |
for idx2, val in enumerate(array): | |
sum2 += val | |
if not hash_map.has_key(sum2): | |
hash_map[sum2] = idx2 | |
sum1 = sum2 - target | |
if hash_map.has_key(sum1): | |
idx1 = hash_map[sum1] | |
if idx2 - idx1 > result: | |
result = idx2 - idx1 | |
seq = array[idx1+1:idx2+1] | |
return result, seq | |
array = np.random.randint(-1000, 1000, size=100) | |
result, seq = find_max_sequence_of_target_sum(array, 0) | |
print result, seq |
No comments:
Post a Comment