*Computer Science & Stuff *

Snippet

Last Updated: August 19, 2024

**Problem:**
Find and return the indices of the two numbers in an array that sum up to the target number.

**Example:**

python`target = 9 arr = [2, 7, 11, 13]`

This involves iterating over each item in the array, finding the sum of the item and other individual items in the array and comparing it to the target.

This approach incolves a nested for loop which means a **time complexity of O(n^2)**

This is how it looks like in python:

python`my_list = [3, 2, 9, 8, 13, 7] target = 9 #Brute Force Method def two_sum(my_list, target): for i in range(len(my_list)): for j in range(i+1, len(my_list)): result = my_list[i] + my_list[j] if result == target: return [i, j] two_sum(my_list, target) #Result: [1,5]`

This method involves passing each item through a hash function and storing it in a hashmap. Here's a step by step of how I solved this:

- Create a hashmap
- Find the difference of each item from the target value. The difference is the second value we need.
- Check if the difference is already in the hashmap. If it isn't, add the number(not the difference) to the table, and move on to the next number in the list.
- If the difference exists in the hash table, return its index and the index of the number in an array.

Now, let's see how it looks in code:

python`my_list = [3, 2, 9, 8, 13, 7] target = 9 #Using a Hash Table def two_sum(my_list, target): prevMap = {} #Create a Hashmap for i, n in enumerate(my_list): diff = target - n if diff in prevMap: return[prevMap[diff], i] prevMap[n] = i two_sum(my_list, target) #Result: [1,5]`

This method has a time complexity of O(n)