LeetCode (Algorithms#1) ‒ Two Sums

Problem

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

Given nums = [2, 7, 11, 15], target = 9,

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

Solution

The brute force solution searches for the two indices in O(n^2) time. The problem can be solved in O(n) time and space using a hash table, where you simply look at each number x, and query the table for target - x.

Note: Use a HashMap to store indices as the values, with a unique integer hash function. The default function for Java's Integer is sufficient.

Time complexity: O(n)
Space complexity: O(n)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

public int[] twoSum(int[] nums, int target) { int[] res = null; Map<Integer,Integer> map = new HashMap<Integer,Integer>(nums.length); for (int i = 0; i < nums.length; i++) { map.put(nums[i], i); } for (int i = 0; i < nums.length; i++) { Integer j = map.get(target - nums[i]); if (j != null && i != j.intValue()) { res = new int[2]; res[0] = i; res[1] = j.intValue(); break; } } return res; }