Enc-2024

Question 1

Given a sequence of positive integers nums and an integer target, return whether there is a continuous sequence of nums that sums up to exactly target.
nums = [1, 3, 1, 4, 23]
target = 8 #True

Answer 1

print(main(nums))

#prefer this prefix approach.
def main(nums):
    prefixSums = set()
    prefixSums.add(0)
    curSum = 0
    for n in nums:
        curSum += n
        diff = curSum - target # 1 + 3 + 1 + 4 - 8 = 1
        if diff in prefixSums:
            return True
        prefixSums.add(curSum)
    return False
# WORKS FOR BOTH POSITIVE AND NEGATIVE
# O(N)
# O(N)

nums = [1, 3, 1, 4, 23]
def main2(nums):
    l = 0
    curSum = 0
    for r in range(len(nums)):
        curSum += nums[r]
        while curSum > target:
            curSum -= nums[l]
            l += 1
        if curSum == target:
            return True
    return False
# print(main2(nums))
#O(N) POSITIVE ONLY
#O(1)