1.Two_Sum_(Easy).md

1. Two Sum (Easy)

Link: https://leetcode.com/problems/two-sum/

Question:

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]

KeyPoints:

I will only explain the keypoints of the alternative solution, which is the fastest solution.
The main idea is that for each element from the beginning of the list, we calculate the difference and find if the difference has been "cached" in the hashmap 'seen'. So that we only need $O(n)$ time to traverse the list and return the indices.

Naive Solution:

class Solution(object):
    def twoSum(self, nums, target):
        # Naive approach
        for i in range(len(nums)-1):
            for j in range(i+1, len(nums)):
                if nums[i]+nums[j] == target:
                    return [i, j]

Time Complexity: $O(n^2)$
Space Complexity: $O(1)$

Alternative Solution:

For each element from $0^\text{th}$ index to the end, we save the remainder of target - nums[i] into hashmap, so we check if the next element is the remainder we needed in seen, we can just return the previous index with i.

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

Time Complexity: $O(n)$
Space Complexity: $O(n)$