Two Sum

 Q:
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

A:

class Solution:
    # @return a tuple, (index1, index2)
    def twoSum(self, num, target):
        myDict = {}
        for idx, value in enumerate(num,start =1):
            if target - value in myDict:
                return [myDict.get(target-value), idx]
            myDict[value] = idx
        

就是先排序。
为了标记出原始的index, 在quicksort的时候，用了一个数组，来记录index的变化

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        // by assuming that each input would have only exactly one solution, 
        // we know that there is no duplicate values
        int[] A = new int[numbers.length];
        //using index to record the sorted index of the input value
        int[] B = new int[numbers.length];
        for(int i = 0; i < numbers.length; i++){
            A[i] = numbers[i];
            B[i] = i+1;
        }
        quickSort(A,0,A.length-1,B);
        
        int[] sumIndex = new int[2];
        for(int i = 0; i < A.length; i++){
            for(int j =i+1; j < A.length; j++){
                if(A[i] + A[j] == target){
                    if(B[i] < B[j]){
                        sumIndex[0] = B[i];
                        sumIndex[1]  = B[j];
                    }else{
                        sumIndex[0] = B[j];
                        sumIndex[1] = B[i];
                    }
                    return sumIndex;
                }else if( A[i] + A[j] > target){
                    break;
                }
            }
        }
        return null;
        
    }
    public void quickSort(int[] A, int p , int r, int[] indexOfA){
        if(p < r){
            int q = partition(A, p,r,indexOfA);
            quickSort(A,p,q-1,indexOfA);
            quickSort(A, q+1, r,indexOfA);
        }
        
    }
    public int partition(int[] A, int p , int r , int[] indexOfA ){
        int key = A[r];
        int i = p-1;
        int tmp;
        for (int j = p; j < r; j++){
            if(A[j] < key){
                i++;
                exchange(A,i,j);                 
                exchange(indexOfA,i,j); 
            }
        }
        exchange(A,i+1,r);        
        exchange(indexOfA, i+1, r);        
        return i+1;
    }
    public void exchange(int[] A, int p, int r){
        int tmp = A[p];
        A[p] = A[r];
        A[r] = tmp;
    }
    
}

-------------other people's solution  ---------------
Seems that there are no better solution.

Tiger,你太自大了。还有two pointer 算法。要用到自己实现的quicksort

--------------------------第二遍-------------------------
用了HashMap,就不用自己写quickSort函数了。 直接调用Arrays.sort（）函数
  但是，对于有重复值的，要加一个比较tricky的操作。

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        int n = numbers.length;
        for (int i = 0; i < n; i++) { // at most two values have the same value, // but this do not work when numbers[i] == 0
            if( target ==0 &&  map.get(0)!=null){ // deal with case that  0+0 = 0,
                int[] result = {map.get(0),i+1};
                return result;
            }
            if (map.get(numbers[i]) == null)
                map.put(numbers[i], i + 1);
            else
                map.put(- numbers[i], i + 1);
        }       
        Arrays.sort(numbers);
        int i = 0, j = n - 1;
        int a = 0, b = 0;
        while (i < j) {
            while (j > i && numbers[i] + numbers[j] >= target) {
                if (numbers[i] + numbers[j] == target) {
                    a = numbers[i];
                    b = numbers[j];
                    break;
                } else {
                    j--;
                }
            }
            i++;
        }
        if(a==b){
            a = Math.abs(map.get(-a)); // get their index
        }else{
            a = Math.abs(map.get(a));
        }
        b =  Math.abs(map.get(b));
        int[] result = { Math.min(a, b), Math.max(a, b) };
        return result;
    }
}

--------------------上面的算法，还是O(n*lg(n))的复杂度。--- 因为排序了。-------------
第三遍 直接利用HashMap来取值。 可以达到O(n)的效率  -----------

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        // number[i]  as the key, and position as the key
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();        
        for(int i =0;i< nums.length; i++){
            int b = target - nums[i];
            if(map.get(b) != null){
                int index1 = map.get(b);
                int [] result = {index1+1, i+1};
                return result;
            }
            map.put(nums[i],i);
        }
        return null;
    }
}

Mistakes：
1： 对于two pointer 算法， 测试二者的和是否相等，应该是在第二个while 里面。
2：  另外， 是index1<index2,而不是各自对应的 value1<value2
3：  不能用HashMap 记录其地址，因为有可能有重复的 。 例如 
输入数组为:  [2,1,9,4,4,56,90,3]   target = 8
 对这道题的临时解决方法是： 因为，是2sum，  所以，最多有2个重复的，  （如果有3个重复， 例如上面的4，4,4， 就会出现多个结果。与题目不符）
---------- HashMap  在put 的时候--如果已经存在， 则put 其value 的负值。
嗯， 这里理解还有个错误， 就是，题意是不允许一个地址，用两遍的。
也就是说，对输入： 【1，2】  target = 2 , 是不允许用两遍1 来sum to 2的。