Two Sum

1 Two Sum

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.

1
2
3
4
5
6

Example:

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

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

Two Sum

Problem Analysis

Since we need to get the indices of numbers in the original array, we can not sort this array. So, what I am going to do, is to store the result and its index in a map.

Algorithm Analysis

Go through the whole array, check if we can find the current number storing in the Map. If not, we store the number of target - current number and the current index in the map. So, in this map, the key will be target - current number and the value will be index of the current number. If we find the current number in the map, we store those two indices into the result static array. Put the index stored in the map at first and the current index for the second one.

Time Complexity Analysis

• Time: O(N)
• Space: O(N)

Code Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
    public int[] twoSum(int[] nums, int target) {
        /* Map : Number, index */
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            if(map.containsKey(nums[i])) {
                return new int[]{map.get(nums[i]), i};
            } else {
                map.put(target - nums[i], i);
            }
        }
        return new int[]{-1, -1};
    }
}

Follow up Question

Do not use additional space.

If we can assume the array was sored, then we can just use two pointers to find the answer.

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

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int start = 0;
        int end = numbers.length - 1;
        
        while(start < end) {
            int sum = numbers[start] + numbers[end];
            if(sum == target) {
                return new int[]{start + 1, end + 1};
            } else if(sum > target) {
                end--;
            } else if(sum < target) {
                start++;
            }
        }
        return new int[]{-1, -1};
    }
}

• ← Previous Post
• Next Post →