Programming with Passion Algorithms, Mobile Development, Robotics

## Saturday, June 25, 2016

### 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:

### 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 map = new HashMap(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; }