EasyLeetCode #1Arrays & Hashing

Two Sum

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.

Constraints

2 <= nums.length <= 10^4, -10^9 <= nums[i] <= 10^9, -10^9 <= target <= 10^9

Examples

Input: nums = [2,7,11,15], target = 9

Output: [0,1]

Because nums[0] + nums[1] == 9, we return [0, 1].

Solution Approach

Use HashMap to store element frequencies or mappings. Iterate through array once to build map, then solve based on stored data. Common for two-sum and anagram problems.

Implementation

# Approach 1: Hash Map (Most Efficient)
def twoSum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

# Approach 2: Two Pointers (For sorted array)
def twoSumSorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return [left + 1, right + 1]
        elif total < target:
            left += 1
        else:
            right -= 1
    return []

# Approach 3: Brute Force (O(n^2))
def twoSumBrute(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(n)

Key Learning Points

HashMap for O(1) lookupsSingle pass solutionComplement/pairing pattern