The objective is to identify two numbers within an integer array that sum up to a specific target value and return their indices. It is assumed that there is exactly one valid solution per input and that an element cannot be used twice.

For example, given the array nums = [2, 7, 11, 15] and target = 9, the function should return [0, 1] becuase nums[0] + nums[1] equals 9.

Brute Force Approach

The most straightforward method involves checking every possbile pair of numbers using nested loops. While easy to implement, this results in a time comlpexity of $O(n^2)$.

class Solution:
    def findPair(self, data, goal):
        length = len(data)
        for x in range(length):
            for y in range(x + 1, length):
                if data[x] + data[y] == goal:
                    return [x, y]

Optimization with Hash Map (Two Pass)

To improve performance, we can reduce the time complexity to $O(n)$ by using a hash map. This approach involves two iterations: first, we map every number to its index. Second, we check if the complement (the value needed to reach the target) exists in the map.

class Solution:
    def findPair(self, data, goal):
        lookup = {}
        # Build the map
        for idx, val in enumerate(data):
            lookup[val] = idx
        
        # Find the pair
        for idx, val in enumerate(data):
            remainder = goal - val
            if remainder in lookup and lookup[remainder] != idx:
                return [idx, lookup[remainder]]

Single Pass Optimization

We can achieve the same $O(n)$ efficiency with only one loop. As we iterate through the list, we check if the complement of the current number is already in our map. If it is, we have found the solution. If not, we add the current number to the map for future checks.

class Solution:
    def findPair(self, data, goal):
        lookup = {}
        for idx, val in enumerate(data):
            needed = goal - val
            if needed in lookup:
                return [lookup[needed], idx]
            lookup[val] = idx