# Continuous sequence against target number

• 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

• @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;
}
``````

• This is brilliant! Thanks so much!

• @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

• positive integers include 1,2,3....so in your case, input can't be [0]

• Ah ok my mistake. I read another version of this problem where nonnegative integers are allowed.

• @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)
Space 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)

• ``````
A= [1, 3, 5, 23, 2]
S= 8
done=0
for i,x in enumerate(A):
if x>S:
continue
j = i
sum = 0
while j<len(A):
sum += A[j]
if sum>S:
break
elif sum==S:
done =(i,j)
break
j+=1
if done:
break

print A[done[0]:done[1]+1]

``````

• @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``````

• ``````def has_sequnce(nums, t):
if not nums or t <= 0: return False
left, right, total = 0, 0, 0

while right < len(nums):
total += nums[right]
right += 1

while total > t:
total -= nums[left]
left += 1

if total == t:
return True

return False
``````

• Actually it's similar to https://leetcode.com/problems/subarray-sum-equals-k/#/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;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.