1.Two_Sum_(Easy).md

1. Two Sum (Easy)

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

Date	Time	Y/N
Jun 11, 25	8m 8s	Y

Hashmap:

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]:
        # Q: Return the indices of two integers from nums sum up to target
        # nums = [2, 4], target = 6
        # nums = [-2, -4], target = -6
        # S: Use hashmap to save a difference of target - nums[i] by index i
        # TC: O(n), n=len(nums), SC: O(n)

        hashmap = {}    # {diff: index}
        for i in range(len(nums)):
            # Check if nums[i] exists in hashmap
            if nums[i] in hashmap:
                return [hashmap[nums[i]], i]
            # Add diff with index i into hashmap
            hashmap[target - nums[i]] = i

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