LeetCode | 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

要求：返回的index值不能直接是数组下标，nums[0]的index为1，且index[0]<index[1]

//基本的brute force方法，可以accept，时间复杂度为O(n^2)
//题目tag提示HashTbale，显然此方法不推荐
public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] index = new int[2];
        for(int i=0; i<nums.length; i++){
            int num_1 = nums[i];
            for(int j=i+1; j<nums.length; j++){
                int num_2 = nums[j];
                if(num_1+num_2 == target){
                    index[0] = i+1;
                    index[1] = j+1;
                    return index;
                }
            }
        }
        return index;
    }
}

//用HashMap：
//向后遍历，遍历过的元素作为备选集合，对每一个元素nums[i]，需要找到needNum=target-nums[i]
//如果能在备选集中找到needNum，那么index=[index_needNum+1, i+1]，否则就把nums[i]也加入备选集
//注意一点：要先确认needNum在备选集中找不到，才能把nums[i]加入备选集。否则如[3,2,4],target=6
//先把3加入备选集，再来找needNum，都不会向后遍历，直接返回[1,1]了
public class Solution {
    public int[] twoSum(int[] nums, int target) {
        
        int[] index = new int[2];
        HashMap<Integer, Integer> myMap = new HashMap<Integer, Integer>();
        
        for(int i=0; i<nums.length; i++){
            int needNum = target - nums[i];
            //myMap.put(nums[i], i);             //put语句不能放在此处，如果target恰为2*nums[i]
            if(myMap.containsKey(needNum)){       //那它只要自己加自己就等于target，就会return [i,i]
                index[0] = myMap.get(needNum) + 1;
                index[1] = i + 1;
                return index;
            }
            myMap.put(nums[i], i);
        }
        
        return index;
    }
}

此外，如果不是要求返回两个元素的index，而是直接返回两个元素，那么也可以用如下形式：

（2015.6.28补充：不要用list或其他容器来维护已便利过的数组，用hashmap，因为其他容器的contains方法比map的contains要慢的多）

（map的contains是直接用key的hash值来计算，再判断的，非常之快。而其他容器如list可能也是通过遍历来确定是否contains的，故而很慢）

//不返回index，而是返回和为target的数
//就无需利用map来额外维护index，只需一个允许重复且拥有contains()方法的容器即可
public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        List<Integer> myList = new ArrayList<Integer>();
        
        for(int i=0; i<nums.length; i++){
            int needNum = target - nums[i];
            if(myList.contains(needNum)){
                result[0] = needNum;
                result[1] = nums[i];
                return result;
            }else{
                myList.add(nums[i]);
            }
        }
        
        return result;
    }
}

或者先排序，再用二分法：

        Arrays.sort(nums);      //注意：排序后元素的index已经被打乱了
        for(int i=0; i<nums.length; i++){
            int tempNum = nums[i];
            int needNum = target - tempNum;
            
            //开始用二分查找，确认needNum的位置
            int head = i+1;
            int tail = nums.length - 1;
            
            while(head <= tail){
                int middle = (head + tail) / 2;
                if(nums[middle] == needNum){
                    result[0] = nums[1];
                    result[1] = nums[middle];
                    return result;
                }else if(nums[middle] > needNum){
                    tail = middle - 1;
                }else if(nums[middle] < needNum){
                    head = middle + 1;
                }
            }
        }

为了进一步降低算法的时间复杂度，对twoSum继续优化。上面只是优化到引入二分查找就没再继续了。

但若用夹逼的思想，则除去排序的O(nlogn)外，只需一次遍历O(n)就一定可以找到一对sum为target的两个值（此处假设nums中只有一对满足要求），代码如下:

    Arrays.sort(nums);             //先对数组进行排序
    int left = 0;
    int right = nums.length - 1;
    while(left < right){
    	if(nums[left]+nums[right] == target){
    		return new int[]{nums[left], nums[right]};
    	}else if(nums[left]+nums[right] > target){
    		right--;
    	}else if(nums[left]+nums[right] < target){
    		left++;
    	}
    }