# Leetcode 1. Two Sum

Description:

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

## Solution 1: brute force with nested for loops

1. First loop: loop for every element starting from index 0. End the loop with last element(len(nums))

2. Second loop: loop for every element starting from the next element where the first loop iterates. End the loop with the last element(len(nums))

3. Check if the sum equals to target or not

4. Time Complexity: O(n^2)

class Solution:
    def twoSum(self, nums: List[int], target: int ) -> List[int]:
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]
        return []

## Solution 2: Hashmap of complement
1. Create a empty hashmap

2. Iterate through the list, and check if the complement of the element is in the map(dictionary) or not. If it's not in the map, store the complement as key and the index as value. If it's in the map, then return the value and the index in a list.

3. complement is calculated by target - element

4. Time Complexity: O(n)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:

        mapping = dict()

        for index, number in enumerate(nums):
            
            complement = target - number
            
            if number not in mapping:
                mapping[complement] = index
            else:
                return [mapping[number], index]
        
        # not found
        return []