Does this solve 3SUM in O(N log(N)) time?

Question

Does this algorithm work as a solution for 3SUM in O(N log(N)) where the problem is defined by Wikipedia as

In computational complexity theory, the 3SUM problem asks if a given set of n real numbers contains three elements that sum to zero.

//Given an array of integers called list
//return true if 3 integers in list sum to 0, false otherwise

//quicksort the provided list
quickSort(list)

//add all elements of the list to a hashmap where the key is a number and the value is the number of times it occurs
hs = new hashMap<Integer, Integer>()
for(Integer i:list)
   if(hs.get(i)==null)
        hs.add(i, 1)
    else
        hs.add(i, hs.get(i)+1)

//create a pair of pointers pointing to the left of right of the center of array
startIndex=0
while (list[startIndex]<0 and startIndex<list.length-1)
startIndex++

left=startIndex
right=startIndex+1

//run this loop while pointers are in boundaries of array
while(! (left<0 or right>=list.length)
{
    //see if a 3rd number that can be added to the numbers at left
    //and right to make 0 can be found
    sum=list[left] + list[right]
    negsum= -(sum)
    //if it's found enter these if statements
    if(hs.get(negsum)!=null)
    {
        //check for the possibility that the 3rd number is one of the 1st 2, if not return true 
       if(negsum==list[left] or negsum== list[right])
       {
        //if the 3rd number is one of the 1st 2 make sure that a duplicate of it exists, or if all 3 are 0, that 3 zeros exist
        //if we have enough duplicates, return true
            if(list[left]==list[right] )
                if(list.hasMoreThanTwo(negsum))
                    return true
            else if(list.hasMoreThanOne(negsum))
                return true
       }
       else
           return true
    }

    //if a trio cannot be formed with the numbers at left and right, adjust the pointers so that we will get closer to 0 and try again.
    if (sum<0)
        right++
    else
        left--
}

//if pointers go out of bounds 3 numbers that sum to 0 don't exist
return false

Answer 1

Your code doesn't handle this case:

[-10, -7, 0, 0, 4, 6].

In this case, the right pointer would go out of bounds because the left pointer would be at -10, which is too big.

So if something is really negative, your algorithm will try to look for a positive solution, and ultimately fail.