0.前言

Given an array of integers that is already sorted in ascending order, 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.
Note:
Your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution and you may not use the same element twice.

1. c++ 版本

方法1：使用双指针

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

方法2：借助map，然后进行find

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> res;
        map<int, int> per_num;
        map<int, int>::iterator iter;
        for (int i=0; i<numbers.size(); ++i) {
            iter = per_num.find(target - numbers[i]);
            if (iter != per_num.end()) {
                res.push_back(iter->second);
                res.push_back(i+1);
                break;
            }
            per_num.insert(make_pair(numbers[i], i+1));
        }
        return res;
    }
};

2. python 版本

class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        res = []
        i, j = 0, len(numbers)-1
        while i < j:
            if target > numbers[i] + numbers[j]:
                i = i+1
            elif target < numbers[i] + numbers[j]:
                j = j-1
            else:
                res.append(i+1)
                res.append(j+1)
                break
        return res