title: Create a function that checks whether an array has two opposite elements or not for less than n^2 complexity. (C++)
body: <p>Create a function that checks whether an array has two opposite elements or not for less than n^2 complexity. Let's work with numbers.</p>
  
  <p>Obviously the easiest way would be:</p>
  
  <pre><code>bool opposite(int* arr, int n) // n - array length
  {
   for(int i = 0; i &lt; n; ++i)
    { 
      for(int j = 0; j &lt; n; ++j)
       {
         if(arr[i] == - arr[j])
            return true;
       }
    }
  
    return false;
  }
  </code></pre>
  
  <p>I would like to ask if any of you guys can think of an algorithm that has a complexity less than n^2.
  My first idea was the following:
  1) sort array ( algorithm with worst case complexity: n.log(n) )
  2) create two new arrays, filled with negative and positive numbers from the original array
  ( so far we've got -> n.log(n) + n + n = n.log(n))
  3) ... compare somehow the two new arrays to determine if they have opposite numbers</p>
  
  <p>I'm not pretty sure my ideas are correct, but I'm opened to suggestions.</p>