Location>code7788 >text

Hash Table Practice -- Sum of Two Numbers

Popularity:705 ℃/2024-09-19 11:48:25

catalogs
  • Background to the topic
  • Ideas for solving the problem


Background to the topic

image

This topic can be accomplished with a regular double loop.
But not the optimal solution. Why?

Look at the number of steps he took:
N =【3,2,4】
Find the coordinates of the two elements whose result is 6 as follows.
1). 3 + 2 = 5 is not equal to
2). 3+4 = 7 is not equal to
3). 2+4 = 6 equals, get coordinates [1, 2].

Laws:
2 numbers = 1 step
3 numbers = 3 steps
4 numbers = 6 steps
5 numbers = 10 steps
6 numbers = 15 steps
7 numbers = 21 steps
......

If there are N elements, then it takes N steps, then denoted as O(N). Analyzed below then the big O of this algorithm is:
image

is approximately equal to N(N) = $ N^2 $

The time complexity of this algorithm is: O($ N^2 $).
Is there any way to reduce this time complexity?

Ideas for solving the problem

image

def twoSum(nums, target).
    # Create a hash table to store the values and indexes
    num_to_index = {}

    # Iterate over the array
    for i, num in enumerate(nums): # Calculate the complement of the current number.
        # Calculate the complement of the current number
        complement = target - num

        # Check if the complement is in the hash table
        if complement in num_to_index.
            # If in, return the complement's index and the current index
            return [num_to_index[complement], i]

        # If not, store the current number and its index into the hash table
        num_to_index[num] = i

    # If no two numbers are found that match the condition, return the empty list or throw an exception
    return []

print(twoSum([3, 2, 4], 6))

Simulate the running process:

# {} create map

# 1) 6 - 3 = 3 , determine that 3 is not in the map, proceed.
# map plus {3:1}

# 2) 6 - 2 = 4 , determine that 4 is not in the map, continue.
# map plus {3:1,2:2}

# 3) 6 - 4 = 2 , determine 2 is in map , return current coordinates of 4 and 2, end.
# map{3:1,2:2}