Intuition

Keep a map of the numbers, and lookup for it’s complement based on target.

Approach

Loop through all elements, check if the complement of the current number is already in the store. In case it’s true, return current index and the index stored. in case it’s not, add the current number to the store.

The key here is to store the current number in the map, not the complement

This solution works here but takes additional space. Another solution that can be applied here is two pointers, since the array is sorted already.

• Start with pointers in the edges (start, end)
• If n1 - n2 > target: end–
• If n1 - n2 < target: start++
• If n1 - n2 == target solution

Complexity

• Time complexity: O(n)

• Space complexity: O(n)

Code

class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        _map = {}

        for i in range(len(numbers)):
            n = numbers[i]
            diff = target - n

            if diff in _map:
                return [_map[diff]+1, i+1]

            _map[n] = i