Question: Given a sequence of positive integers A and an integer T, return whether there is a continuous sequence of A that sums up to exactly T
Example
[23, 5, 4, 7, 2, 11], 20. Return True because 7 + 2 + 11 = 20
[1, 3, 5, 23, 2], 8. Return True because 3 + 5 = 8
[1, 3, 5, 23, 2], 7 Return False because no sequence in this array adds up to 7
Continuous sequence against target number


@ngocbaopt isn't it possible to tag the company ?
My solution used sliding window. The window expands to the right when current sum is less than T, it shrinks from left when sum is greater than T and algorithm return true in case current sum is T.boolean hasSequence(int[] nums, int T) { if (T <=0) return false; if (nums.length == 0) return false; int i = 0; int start = 0; int sum = 0; while (i < nums.length) { if (sum + nums[i] < T) sum += nums[i]; else if (sum + nums[i] == T) return true; else { sum += nums[i]; while (sum > T) { sum = nums[start]; start++; } if (sum == T) return true; } i++; } return false; }

@elmirap what if T == 0, they never said it could not be 0. If T == 0 and u had input array [0] (which is allowed since we can have nonnegative numbers) then urs fails I think


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




@ngocbaopt was this phone or onsite interview? Did you start off w/ brute force first or just go straight into the sliding window approach?


@ridz seems that the algorithm pass through each item once Therefore time complexity is O(n)