---
# System prepended metadata

title: \#167 Two Sum II - Input array is sorted
tags: [leetcode, leetcode-easy]

---

# \#167 Two Sum II - Input array is sorted
## *給定數字陣列與target, 回傳兩數加總為target的陣列index*
## Log
 - build 20210408 by syhuang

## 前後夾擊
 - 因為已經排序過, 從陣列頭尾開始加總比較target並移動, 降低空間複雜度為O(1)
```javascript=
var twoSum = function(numbers, target) {
    var tail = 0;
    var head = numbers.length-1;
    var sum = numbers[tail] + numbers[head];
    while(sum != target){
        if(sum<target)tail++;
        if(sum>target)head--;
        sum = numbers[tail] + numbers[head];
    }
    return [tail+1,head+1];
};
```
## 初見
 - 同#1解法, 用map存target與目前數字的差, 當map當前數字有值就表示兩數加總為target
```javascript=
var twoSum = function(numbers, target) {
    var diffMap = new Map();
    var result = [];
    for(var i=0; i<numbers.length; i++){
        if(diffMap.has(numbers[i])){
            result.push(diffMap.get(numbers[i])+1);
            result.push(i+1);
            return result;
        }
        diffMap.set(target-numbers[i],i);
    }    
};
```
## 備註
## 參考
###### tags: `leetcode`, `leetcode-easy`