Continuous sequence against target number


  • 5
    N

    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


  • 16

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

  • 0
    N

    This is brilliant! Thanks so much!


  • 0
    I

    @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


  • 0
    N

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


  • 0
    I

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


  • 0

    @elmirap cool solution~


  • 3

    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)


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

  • 0
    L

    @elmirap Cool solution! What's the time complexity of your solution? Anybody knows?


  • 0
    N

    @linxingquan i believe it's O(n)


  • 0

    @linxingquan yes its O(n)


  • 1
    I

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


  • 0
    R

    @elmirap Would't the time complexity be O(n^2) in worst case ?


  • 0

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


  • 0
    S
    
    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]
    
    

  • 0
    Z

    @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

  • 0
    A
    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
    

  • 0

    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.


  • 0
    S

    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;
      }
    

Log in to reply
 

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