Problem:

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

Method 1:

Use two for loops. Time complexity is O(n^2). Bad and slow.

Code for method 1:

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        int id1 = 0;
        int id2 = 0;
        
        for (id1 = 0; id1 < nums.length; id1++){
            for (id2 = id1 + 1; id2< nums.length; id2++){
                if (nums[id1] + nums[id2] == target){
                    res[0] = id1+1;
                    res[1] = id2+1;
                    return res;
                }
            }
        }
        
        return res;
    }
}

Method 2: by Hash Table

This is a very cool method!!!

Key: the numbers in the array

Value: index

When we encounter a value nums[i], we want to know if we already encountered (target-nums[i]). Hash table helps to quick look it up.

Time complexity: O(n)

Code for method 2: 

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        if (nums == null || nums.length < 2 ) return res;
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        
        for (int i = 0; i < nums.length; i++){
            if (!map.containsKey(target - nums[i])){
                map.put(nums[i],i);
            }else{
                res[0] = map.get(target - nums[i]) + 1 ;
                res[1] = ++i;
                break;
            }
        }
        return res;
    }
}

Method 3:

By using two pointers.

  • Copy the array to a new array and sort it . Details: System.arraycopy(nums,0, sorted, 0,nums.length);  Arrays.sort(sorted)
  • Have two points, one at the beginning, one at the end. And then move then towards the center of the array.
  • Once find the two numbers adding up to target, go on to find their index in the original array.
  • Sort the result array.

Time complexity:

O(nlogn)

Code for method 3:


public class Solution {
    public int[] twoSum(int[] nums, int target) {
        // copy and sort the original array;
        int[] sorted = new int[nums.length];
        System.arraycopy(nums, 0, sorted, 0, nums.length);
        Arrays.sort(sorted);
        
        int first = 0;
        int second = nums.length-1;
        
        while (first < second){
            if (sorted[first] + sorted[second] < target){
                first ++;
                continue;  
            }else if (sorted[first] + sorted[second] > target){
                second --;
                continue;
            }else{
                break;
            }
        }
        // find the indexs for sorted[first] and sorted[second]
        int index1 = -1;// so that we knwo whether it has to be copyed or not
        int index2 = -1;
        for (int i = 0; i < nums.length; i++){
            if (nums[i] == sorted[first] || nums[i] == sorted[second]){
                if (index1 == -1){
                    index1 = i+1;
                }else{
                    index2 = i+1;
                }
            }
        }
        // remeber to sort the result. 
        int[] res = {index1, index2};
        Arrays.sort(res);
        return res;
    }
}