[LeetCode] 1. Two Sum

Posted on | In

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, and you may not use the same element twice.

Example:

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

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

Explanation

  1. We can use a HashMap to solve this problem because HashMap uses $O(1)$ to find the key.

  2. Iterate the array, store the element as key, index as value. But before we store, we first check if the map contains the element we want to find, which is target - nums[i]. If the map already have this value we want to find, then we can return the result with current index and map.get(target-nums[i]).

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        HashMap<Integer, Integer> hm = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int find = target - nums[i];
            if (hm.containsKey(find)) {
                res[0] = hm.get(find);
                res[1] = i;
                break;
            }
            hm.put(nums[i], i);
        }
        return res;
    }
}