@elmirap cool solution~
Store cumulative sums in an array say 'C' (can be done in O(n) ) and then find two numbers in 'C' whose difference is T using hashmap ( in O(n) ).
Total time Complexity: O(n)
arg1 = [23, 5, 4, 7, 2, 11] arg2 = [1, 3, 5, 23, 2] def check(arg, sm): # Avoid recursive function if number exist in list for i, val in enumerate(arg): if val == sm: return True # Start from 0 to n index and check if any sequence has sum == argument for i in range(len(arg)): s = rec_func(arg[i:], sm) if s: return True return False # Check if sum is possible to argument for any continuous sequence def rec_func(listnum, remainAmount, lasti=None): if remainAmount == 0: return True elif remainAmount > 0: for i in range(len(listnum)): n = listnum[i] if lasti is None: if n <= remainAmount: remainAmount -= n lasti = i else: remainAmount -= n lasti = i return rec_func(listnum[i+1:], remainAmount, i) else: return False print(check(arg1, 13)) # True print(check(arg1, 20)) # True print(check(arg1, 22)) # False print(check(arg2, 8)) # True print(check(arg2, 7)) # False
@elmirap Cool solution! What's the time complexity of your solution? Anybody knows?
@linxingquan i believe it's O(n)
@linxingquan yes its O(n)
@ngocbaopt was this phone or onsite interview? Did you start off w/ brute force first or just go straight into the sliding window approach?
@elmirap Would't the time complexity be O(n^2) in worst case ?
@ridz seems that the algorithm pass through each item once Therefore time complexity is O(n)
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.