Thursday, August 13, 2015

all pairs in array that sum to k

//example:
k = 5
a    :  1  3  4  5  6  7  2  2 -1
delta:  4  2  1  0 -1 -2  3  3  6 // delta = k - a[i]
pairs: (1,4), (3,2), (3,2), (6,-1)

k = 5
a:     3 3 2 3
delta: 2 2 3 2
pairs: (3,2), (3,2), (2,3)
// O(n) time, O(n) space
(a, k):
    pairs = new
    map ncountmap = new
    for i = 0, i < a.length(), i++:
        n = a[i]
        delta = k - n
        dcount
        ncountmap.trygetvalue(delta, out dcount)
        for c = 0, c < dcount, c++:
            pairs.add({delta, n})
        ncount
        ncountmap.trygetvalue(n, out ncount)
        ncountmap[n] = ncount + 1
    return pairs

No comments:

Post a Comment