###### tags: `Leetcode` `medium` `pointer` `binary search` `python` `c++`

# 167. Two Sum II - Input Array Is Sorted

## [題目連結:] https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/

## 題目:
Given a **1-indexed** array of integers numbers that is already **sorted in non-decreasing order**, find two numbers such that they add up to a specific ```target``` number. Let these two numbers be ```numbers[index1]``` and ```numbers[index2]``` where ```1 <= index1 < index2 <= numbers.length```.

Return the indices of the two numbers, ```index1``` and ```index2```, **added by one** as an integer array ```[index1, index2]``` of length 2.

The tests are generated such that there is **exactly one solution**. You **may not** use the same element twice.

* Your solution must use only constant extra space.

**Example 1:**

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

**Example 2:**

Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

**Example 3:**

Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

## 解題想法:
* 求數組中兩數和等於target:
* 一定有解
* index起始訂為1
* 限制要常數space
* 使用pointer
* 頭尾移動判斷和即可

## Python:

class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        #因為已經排好了 用兩個pointer
        head=0
        tail=len(numbers)-1
        while head<tail:
            if numbers[head]+numbers[tail]==target:
                return [head+1,tail+1]
            elif numbers[head]+numbers[tail]>target:
                tail-=1
            else:
                head+=1

result = Solution()
numbers = [2,7,11,15]
target = 9
ans = result.twoSum(numbers,target)
print(ans)

## C++:

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left=0, right=numbers.size()-1;
        vector<int> res;
        while (left<right){
            if (numbers[left]+numbers[right]==target){
                res.push_back(left+1);
                res.push_back(right+1);
                return res;
            }
            else if (numbers[left]+numbers[right]>target)
                right-=1;
            else
                left+=1;
        }
        return res;
    }
};

int main(){
    Solution res;
    vector<int> numbers={2,7,11,15};
    vector<int> ans=res.twoSum(numbers,9);
    for (auto pos: ans){
        cout<<pos<<endl;
    }
    return 0;
}