Thursday, August 06, 2015

subarray with sum k in array

Works for non -ve numbers only.
//example
k = 10

10 1 2 3 5
 |   .   .
     |---|

// fails for -ve numbers
-2 10 3
// time O(n), space O(1)
(a, k):
    maxstart = 0, maxend = -1
    start = 0
    for i = 0, i < a.length, i++:
        sum += a[i]
        while start < i && sum > k:
            sum -= a[start]
            start++
        if sum == k:
            end = i
            if end-start > maxend-maxstart:
                maxstart = start
                maxend = end
    if maxend == -1:
        return -1, -1
    return maxstart, maxend
When a has -ve numbers use the same approach as subarray with sum 0.
//example
k = 10

    a:  1  2  8 -1 -10  3  2  7  8 -1
  sum:  1  3 11 10   0  3  5 12 20 19
sum-k: -9 -7  1  0 -10 -7 -5  2 10  9
                     |-----------|

    a:  -2  8  2
  sum:  -2  6  8
sum-k: -12 -4 -2
            |--|

k = -3

    a: 2 -6  3
  sum: 2 -4 -1
sum-k: 5  1  2
          |--|
// time O(n), space O(n)
(a, k):
    maxstart = 0, maxend = -1
    sum = 0
    sumtoindexMap = new //int->int
    sumtoindexMap[0] = -1
    for i = 0, i < a.length, i++:
        sum += a[i]
        if sumtoindexMap.has(sum -k):
            start = sumtoindexMap[sum -k] +1
            end = i
            if end-start > maxend-maxstart:
                maxstart = start
                maxend = end
        if !sumtoindexMap.has(sum):
            sumtoindexMap[sum] = i
    if maxend == -1:
        return -1, -1
    return maxstart, maxend
Get all subarrays.
//example
    a: 1 0 5 -6 5 0  5
  sum: 1 1 6  0 5 5 10
sum-k: 4 4 1 -5 0 0  5
       . |-|    . .  .
       .   |    . .  .
       |--------| .  .
       .        | .  .
       |----------|  .
                |-|  .
                  |--|
                     |
// time O(n), space O(n)
(a, k):
    items = new
    sumtois = new //int->list{int}
    sumtois[0] = [-1]
    for i = 0, i < a.length, i++:
        sum += a[i]
        if sumtois.has(sum -k):
            for index in sumtois[sum]:
                items.add(tuple(index+1, i))
        indexs = null
        if sumtois.has(sum):
            indexs = sumtois[sum]
        else:
            indexs = new
            sumtois[sum] = indexs
        indexs.add(i)
    return items

No comments:

Post a Comment