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)

@ngocbaopt Here is my solution in python 2.7
def continuousSum(a, t): if len(a) == 0: return False i = 0 tSum = 0 start = 0 while i < len(a): if (tSum + a[i]) < t: tSum += a[i] elif (tSum + a[i]) == t: return True else: tSum += a[i] while tSum > t: tSum = a[start] start += 1 if tSum == t: return True i += 1 return False

Actually it's similar to https://leetcode.com/problems/subarraysumequalsk/#/description. We could use simple prefix sum to check if we have a continuous sequence.

My Java solution using prefix sum to finish it with O(n) time complexity
public boolean hasSequence(int[] nums, int target){ if(nums == null  nums.length == 0){ return false; } int n = nums.length; int[] sums = new int[n + 1]; for(int i = 1; i <= n; i++){ sums[i] = sums[i  1] + nums[i  1]; } int i = 0, j = 1; while(j <= n){ if((sums[j]  sums[i]) < target){ j++; } else if ((sums[j]  sums[i]) > target){ i++; } else { return true; } } return false; }