Subtract each value from the target, see if the difference exists in the list

Solution Breakdown

• Since a sum is a result of two operands added together, we can express it as -> x + y = sum

• By rearranging the equation, we can also express it as -> y = sum - x

• If we have the sum set to our given target value, and let x be represented by each individual values in our list, we can generate the y value

  • Each time we generate the y value, we can search the list if the y value exists in the list

  • If the value exists, the index of x and y will be our pair that generated our desired target value

Example of looking at differences

list = [2,7,11,15]; target = 9

all possible differences:
    9 - 2 = 7
    9 - 7 = 2
    9 - 11 = -2
    9 - 15 = -6

Depending what our target value is, the sum generated by each possible pair creates such numbers. As long as the target value is one of the results (9, 13, 17, 18, 22, 26), we should be able to locate the two index values that adds up to the target.

Pseudocode

# INSERT PSEUDOCODE HERE

Python Solution

def twoSum(array: list[int], target: int) -> list[int]:
    answer = []
    
    for i in range(len(nums)-1):
        diff = target - nums[i]
        for j in range(i+1, len(nums)):
            if nums[j] == diff:
                answer.append(i)
                answer.append(j)
                return answer

    return []
# end of twoSum()

Code Explanation

asd

Optimizing the Solution with a Dictionary

def twoSum(array: list[int], target: int) -> list[int]:
    table = {} # Empty dictionary initialization

    # Loop 1 -> Construct a dictionary
    # Each item = (number in the list, a list of where it is located)
    for i in range(len(nums)):
        current_num = nums[i]
        if current_num not in table:
            # if we haven't seen this number, add it as a key with its index as a singleton list
            table[current_num] = [i]
        else:
            # if we have sen this number before, append its index into the index list
            table[current_num].append(i)
    # end of for loop
    
    # Loop 2 -> Traverse our dictionary and find the sum pairs
    for current_num, locations in table.items():
        diff = target - current_num
        if diff in table:
            # The difference is a key/member of our dictionary
            if diff == current_num:
                # Scenario 1: the difference is equal to the current number
                if len(locations) < 2:
                    # if there were no duplicates of the same number, then we can't create a sum
                    # continue just tells python to ignore the rest of this code block and go to the next iteration
                    continue
                else:
                    # Since the same number occurs in different index locations,
                    # we can slice for the first two values
                    return locations[:2]
            else:
                # Scenario 2: the difference is not equal to the current number,
                # so we just grab index locations of each and return the index list
                index1 = locations[0]
                index2 = table[diff][0]
                return [index1, index2]
    # end of for loop
                    
    return []
# end of twoSum()

Doing only a single traversal through the dictionary

def twoSum(array: list[int], target: int) -> list[int]:
     table = {}
     
     for i in range(len(array)):
          current_num = array[i]
          diff = target - current_num
          
          if diff in table:
               return [table[diff], i]
          
          table[current_num] = i
     
     return []

Connected Readings

• Functions (Link)

• Type Hinting Functions (Link)

• List (Link)

• Dictionary (Link)