prefix sum

[KevinACoder]

//303. Range Sum Query – Immutable
type NumArray struct {
    sums  []int
}

func NewNumArray(nums []int) (na *NumArray) {
    na = &NumArray{}
    na.sums = make([]int, len(nums) + 1)
    for i := 1; i <= len(nums); i++  {
        na.sums[i] = na.sums[i - 1] + nums[i - 1]
    }
    return
}

func (na *NumArray) SumRange(i, j int) int {
    if j >= len(na.sums) || i < 0 || i > j {
        panic("index out of range")
    }
    return na.sums[j + 1] - na.sums[i]
}

[KevinACoder]

""" 523. Continuous Subarray Sum """
def checkSubarraySum(nums, k):
    if k <= 0 :
        return True
    sumIdx = {} #store the first index for a specific range sum
    sumIdx[0] = -1
    sumVal = 0
    for i in range(len(nums)):
        sumVal += nums[i] #update the sum [0:i]
        sumVal %= k #modulo sum
        if sumVal in sumIdx: #if exists a range sum equal current one
            #then we are expected to get a sum divisble by k
            if i - sumIdx[sumVal] > 1: #if the range is large enough
                return True
        else:
            sumIdx[sumVal] = i #record the sum as well as start idx
    return False

[KevinACoder]

""" 525. Contiguous Array """
def findMaxLength(nums):
    sumIdx = {}
    sumIdx[0] = -1
    sumVal = 0
    maxLen = 0
    for i in range(len(nums)):
        #count the number of 0 and 1
        if nums[i] == 1:
            sumVal += 1
        else:
            sumVal -= 1

        if sumVal == 0: #balanced, has equal 0 and 1, find range [0:i]
            maxLen = max(maxLen, i + 1) #include the start point, has length at least 1
        elif sumVal in sumIdx: #have range [x:i]
            maxLen = max(maxLen, i - sumIdx[sumVal]) #exclude the start point
        else: #record sum and start index
            sumIdx[sumVal] = i

    return maxLen        

[KevinACoder]

""" 437. Path Sum III """
def numberOfPaths(root, remain):
    if root == None:
        return 0
    remain -= root.val
    if remain == 0:  # find one path to target
        return numberOfPaths(root.left, remain) + numberOfPaths(root.right, remain) + 1
    else:
        return numberOfPaths(root.left, remain) + numberOfPaths(root.right, remain)

def pathSum(root, target):
    if root == None:
        return 0
    return numberOfPaths(root, target) + pathSum(root.left, target) + pathSum(root.right, target)