Continuous sequence against target number


  • 0

    @elmirap cool solution~


  • 2

    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]
    
    

Log in to reply
 

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