Sweaty Imposter

Two Sum

EasyArrays & HashingBlind 75JuniorOpen on LeetCodeUpdated

You're given an array of integers nums and an integer target. Return the indices [i, j] of the two different positions whose values add up to target, in either order. Exactly one valid pair exists. You may not use the same index twice, although two different positions can hold the same value.

Examples

nums = [2,7,11,15], target = 9 returns [0,1]

nums[0] + nums[1] = 2 + 7 = 9, and no other pair sums to 9.

nums = [3,2,4], target = 6 returns [1,2]

2 + 4 = 6. Using the 3 at index 0 twice would also make 6, but the same index can't be used twice.

nums = [3,3], target = 6 returns [0,1]

The two 3s sit at different indices, so together they form a valid pair.

Constraints

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

Hints

Hint 1

For each number, you know exactly what value its partner would need to be. How could you check whether you've already seen that value without rescanning?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Scan once while remembering every value already passed and its index in a hash map. At index i the partner you need is target - nums[i]; if it's already in the map, that earlier index and i are the answer. Otherwise store nums[i] -> i and move on. Checking before storing means an element can never pair with itself. One pass replaces the O(n^2) check of every pair.

Time

O(n)

Space

O(n)

Pitfall

Storing nums[i] before checking for its complement lets an element pair with itself: for nums = [3,2,4], target = 6 you'd return [0,0] from 3 + 3. Sorting first is also a trap, because it loses the original indices.

Solutions

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];
            if (seen.containsKey(need)) {
                return new int[]{seen.get(need), i};
            }
            seen.put(nums[i], i);
        }
        return new int[0];
    }
}
Drill This