### 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<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; } |

## No comments:

## Post a Comment