title: Two sum running time O(n^2) or O(n)
body: <p>For the two sum problems, find two numbers in a list that adds up to the target. </p>
  
  <p>My solution is to create a dictionary/hash_table, and then store everything in it as <code>(value, index)</code> [Note: For duplicate numbers in the list: higher index would override lower index]</p>
  
  <p>Then traverse through the list again to find the other item. </p>
  
  <pre><code>def twoSum(nums, target): 
      lookup = dict((v, i) for i, v in enumerate(nums))
      for i, v in enumerate(nums):
          if target - v in lookup and i != lookup[target-v]:
              return [lookup[target - v], i]
  </code></pre>
  
  <p>I think the above algorithm would take O(n * n/2) =, hence O(n^2) time but I see some others say that it only takes linear time. Can someone confirm on this? </p>