3.1 Two Sums I

3.1.1 Problem Metadata

3.1.2 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.

3.1.3 Examples

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]

3.1.4 Constraints

  • 2 <= nums.length <= 10^4
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9
  • Only one valid answer exists

3.1.5 Solution - Hash Table Approach

3.1.5.1 Walkthrough

Use a HashMap to store each element and its associated index as key-value pairs \(<\)nums[i], i\(>\).

For each element nums[i], calculate diff = target - nums[i] and check if diff exists in the HashMap: - If yes: return the indices [map.get(diff), i] - If no: store current element and index map.put(nums[i], i)

This allows us to find the complement in O(1) time.

3.1.5.2 Analysis

  • Time Complexity: O(n) - Single pass through array, each lookup/insert is O(1)
  • Space Complexity: O(n) - Hash map stores up to n elements

Why Hash Table? The unsorted array prevents using 2.1">Two Pointers because sorting would destroy the original indices we need to return. Hash table provides O(1) complement lookup while preserving index information.

Why Not Two Pointers? Consider nums = [3,2,4], target = 6. The correct answer is [1,2] (indices of 2 and 4). If we sorted to [2,3,4], the indices would become [0,1], losing the original positions.

Trade-off: We sacrifice O(n) space to maintain O(n) time and preserve indices.

3.1.5.3 Implementation Steps

  1. Initialize an empty HashMap<Integer, Integer> to store <value, index> pairs.
  2. For each index i from 0 to nums.length - 1:
    1. Compute diff = target - nums[i].
    2. If diff is already in the map, return [map.get(diff), i].
    3. Otherwise, record the current value with map.put(nums[i], i).
  3. Return an empty array (the problem guarantees this line is unreachable).

3.1.5.4 Code - Java

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();

    for (int i = 0; i < nums.length; i++) {
        int diff = target - nums[i];

        if (map.containsKey(diff)) {
            return new int[]{map.get(diff), i};
        }

        map.put(nums[i], i);
    }

    return null;
}

3.1.5.5 Code - Golang

func twoSum(nums []int, target int) []int {
    m := make(map[int]int)

    for i, num := range nums {
        diff := target - num        
        result, found := m[diff]

        if found {
            return []int{result, i}
        }

        m[num] = i;
    }

    return nil;    
}

3.1.6 Solution - Storing Difference

3.1.6.1 Walkthrough

Similar to the previous approach, but instead of storing the current number, store the difference (target - nums[i]) in the hash map.

3.1.6.2 Analysis

  • Time Complexity: O(n) - Single pass, O(1) operations per element
  • Space Complexity: O(n) - Hash map stores differences

Comparison with Previous Approach: Both solutions have identical complexity. The first approach stores <value, index> and checks for complements; this approach stores <complement, index> and checks for values. Choose based on readability preference—most implementations favor the first approach as it’s more intuitive.

3.1.6.3 Code - Java

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();

    for (int i = 0; i < nums.length; i++) {
        int num = nums[i];

        if (map.containsKey(num)) {
            return new int[]{map.get(num), i};
        }

        int diff = target - nums[i];
        map.put(diff, i);
    }

    return null;
}

3.1.6.4 Code - Golang

func twoSum(nums []int, target int) []int {
    m := make(map[int]int)

    for i, num := range nums {        
        result, found := m[num]

        if found {
            return []int{result, i}
        }

        diff := target - num
        m[diff] = i;
    }

    return nil;    
}