Problem
Given a list of integers and a target, return two distinct indices whose values add to the target. Return None in Python or null in Java if no pair exists.
Worked example
For [4, 1, 6, 2] with target 8, return (2, 3).
Insert 4 at index 0 and 1 at index 1. At index 2, 6 needs 2, which has not appeared yet. At index 3, 2 needs 6, and the map returns index 2.
How the solution works
The map contains only earlier indices, so the first match gives two distinct indices. Every pair can be found when the algorithm visits its later index.
Checking the map before insertion prevents a single 4 from being used twice when the target is 8. The Java version uses long for the complement so integer overflow cannot produce a false match.
Python solution
def two_sum(nums, target):
seen = {}
for index, value in enumerate(nums):
complement = target - value
if complement in seen:
return seen[complement], index
seen[value] = index
return NoneJava solution
import java.util.*;
class Solution {
static int[] twoSum(int[] nums, int target) {
Map<Long, Integer> seen = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
long value = nums[i];
Integer earlier = seen.get((long) target - value);
if (earlier != null) return new int[]{earlier, i};
seen.put(value, i);
}
return null;
}
}Complexity and edge cases
Expected O(n) time and O(n) space. [3, 3] with target 6 returns (0, 1); [3] with target 6 has no pair; [−4, 1, 5] with target 1 returns (0, 2).
Related exercise: Find the First Unique Character.
Comments
Post a Comment