Two Sum LeetCode

思路1： 利用Hash将数组从左到右扫一遍，把target - numbers[i]存到HashMap里面，这样做可以不需要将所有数都扫一遍，Time O(n） Space O(n)
思路2：（Two pointers）将头尾两个数加起来和target比，比target大，就移动将尾部的pointer向左移动，如果比target小就将头部的pointer向右移动。


public class TowSum {
public static void main(String[] args) {
int[] test ={20,21,25,30,75};
System.out.println(Arrays.toString(twoSum2(test,100)));
}

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

//如果是已经排好序的数据，时间O（n）space O（1）
//为3Sum做准备
public static int[] twoSum2(int[] numbers, int target){
int start = 0;
int end = numbers.length - 1;
while(start < end){
int runningSum = numbers[start] + numbers[end];
if(runningSum == target) return new int[]{start + 1, end + 1};//start + 1这个不是index，而是第几个数
else if (runningSum > target) end--;
else start++;
}
return null;
}
}