Two Sum

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

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

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

This problem is the basic of K Sum problem, which I will illustrate more in the following paragraphs.

The brute force method is simple, you search every pair of combinations of element and see if the target is the sum of the pair, takes O(n^2) time.

Second method takes the order of the numbers into consideration. Take the given example, if you are searching for target 9, you don’t even need to check the 11 and 15. So we sort the list first, and use two pointer to scan from head and tail to the middle, if target is larger than the current sum, we increase the left pointer. if target is smaller, we decrease the right pointer, until we hit the target. Since the pointer is the index of the sorted array, we need to scan again over the original array to get the index in the original array.
Sorting takes nlogn time, and scan over the array from head tail to the mid takes n time, finding the original index also takes n time. So total runtime is O(nlogn).

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] original = new int [numbers.length];
        //copy the original array to find the original index
        for (int i = 0; i < numbers.length; i++) {
            original[i] = numbers[i];
        }
        Arrays.sort(numbers);
        int l = 0;
        int r = numbers.length-1;
        // right move first, find the first index from right that is less than target. 
        while(l < r) {
            if (numbers[r] + numbers[l] > target) {
                r--;
                continue;
            }
            if (numbers[r] + numbers[l] < target) {
                l++;
                continue;
            }
            
            int index1 = -1;
            int index2 = -1;
            // find the original index 
            for (int i = 0; i < numbers.length; i++) {
                if (index1 == -1 && numbers[l] == original[i])
                    index1 = i+1;
                else if (numbers[r] == original[i])
                    index2 = i+1;
            }
            int [] res = {index1, index2};
            Arrays.sort(res);
            return res;
            
        }
        return null;
    }
}

The third method is like the brute force method. We pick a number in the array, but instead of searching the other number in the rest of the array, we pre-process the array and put it into a hashMap, thus, searching each pair takes only constant time. So the total runtime will be O(n).
Notice when searching for another number in your pair, you need to rule out the first element. However, if there are duplicate elements in the array, hashMap can not tell if it is a duplicate or it is the same element. The way to solve this problem is to add the element while searching, adding those has been scanned in to the set and check the set for the next element. The code is also simpler.

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        HashSet<Integer> set = new HashSet<Integer>();
        // put element in the array into a hash set
        int n1 = 0;
        int n2 = 0;
        for (int i = 0; i < numbers.length; i++) {
            if (set.contains(target-numbers[i])) {
                n1 = target-numbers[i];
                n2 = numbers[i];
                break;
            }
            else {
                set.add(numbers[i]);
            }
        }
        
        //find original index
        int index1 = -1;
        int index2 = -1;
        for (int i = 0; i < numbers.length; i++) {
            if (n1 == numbers[i] || n2 == numbers[i]) {
                if (index1 == -1)
                    index1 = i+1;
                else {
                    index2 = i+1;
                    break;
                }
            }
        }
        int [] res = {index1, index2};
        Arrays.sort(res);
        return res;
    }
}