# Leetcode 167. Two Sum II - Input array is sorted

Runtime: 0 ms
faster than 100.00%

Memory Usage: 38.7 MB
less than 97.61%

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        // 設兩個指針，一個在頭一個在尾
        int first=0,second=numbers.length-1;
        int[] result=new int[2];
        
        while(true){
            if(numbers[first]+numbers[second]==target){
                result[0]=first+1;
                result[1]=second+1;
                break;
            }
            else if(numbers[first]+numbers[second]<target){
                first++;
            }
            else 
                second--;
            
        }
        
        return result;
    }
}

解題思維:
第一個想到的是暴力解，巢狀兩個for loop，但這個時間複雜度O(n²)不是我們想要的。
我們可以用雙指針的方式求解，因為是**已排序**的遞增陣列，右邊一定比左邊的值來的大，以刪去的方式思考，刪去不可能的數值，在陣列的左右兩側各放一個指針，當 l 及 r 指到的位置相加小於target，則 l 指針向右1格，反之，則 r 指針向左1格，直到等於target的數值，這樣就可以把時間複雜度降到O(n)

Time complexity: O(n), n個元素最多只會被造訪1次
Space complexity: O(1), 只用到兩個指針

---
Runtime: 2 ms
faster than 28.76%

Memory Usage: 41.7 MB
less than 17.06%

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

解題思維:
建一個HashMap，去尋找出key value對應。

###### tags:`Two Pointer` `Hash Table`