Monday, September 6, 2010

sum to 0

Given a list of n integers (negative and positive), not sorted and duplicates allowed, you have to output the triplets which sum to 0
Pubblicato da a
Reazioni: 

1 comment:

  1. I could think of O(n^2logn) solution
    First sort the array - O(nlogn).
    Then take three pointers - i,j,k
    for i from 1 to n-2:
    j = i+1
    k = n
    while j < k:
    if a[i]+a[j]+a[k] == 0:
    return (i,j,k)
    if a[i]+a[j]+a[k] > 0:
    k--
    else:
    j++

    ReplyDelete

Subscribe to: Post Comments (Atom)