class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
Time: O(n * log(n))
Space: O(n)
"""
# Time: O(n * log(n))
# Space: O(n)
lookup_table = dict((n, i) for i, n in enumerate(nums))
lookup = lookup_table.get
# Find the matching number to sum up to target
# Time: O(n * log(n))
# Space: O(1)
for i, n in enumerate(nums):
j = lookup(target  n)
if j is not None and i != j:
return (i, j)
Readable Python solution [42ms]


Another solution based on sorting the numbers, then finding the pair with bidirectional searching [43ms]:
class Solution(object): def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] Time: O(n * log(n)) Space: O(n) """ # Sorted indices si = range(len(nums)) si.sort(key=lambda i: nums[i]) # Bidirectional search for suitable (a, b) pair, so a + b == target i = 0 j = len(nums)  1 while i < j: delta = nums[si[i]] + nums[si[j]]  target if delta > 0: j = 1 elif delta < 0: i += 1 else: return (si[i], si[j])
It has practically the same complexity and speed as the first solution above. Memory consumption is more predictable due to the use of sorted list instead of dict (hash table).