1. 题目

1.1 英文题目

Given an 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.

Return the indices of the two numbers (1-indexed) as an integer array answer of size 2, where 1 <= answer[0] < answer[1] <= numbers.length.

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

1.2 中文题目

一个有序数组，找到两个数和等于特定数的位置。

注意：索引从1开始并且数组中的一个元素只能用一次。

1.3输入输出

输入	输出
numbers = [2,7,11,15], target = 9	[1,2]
numbers = [2,3,4], target = 6	[1,3]
numbers = [-1,0], target = -1	[1,2]

1.4 约束条件

2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers is sorted in non-decreasing order.
-1000 <= target <= 1000
The tests are generated such that there is exactly one solution.

2. 分析

2.1 暴力求解法

这一题首先可以利用暴力求解法，遍历所有可能的组合，复杂度为O(\(n^{2}\)),代码如下：

class Solution {

public:

    vector<int> twoSum(vector<int>& numbers, int target) {

        vector<int> result(2);

        for (int i = 0; i < numbers.size() - 1; i++)

        {

            for (int j = i + 1; j < numbers.size(); j++)

            {

                if (target - numbers[i] == numbers[j])

                {

                    result = { ++i, ++j };

                    break;

                }

            }

        }

        return result;

    }

};

这种方法运行效率太低，而且没有利用数组有序的条件

2.2 哈希表法

这种方法是参考leetcode第一题的解法，第一题和该题唯一的差异是第一题数组无序，因此第一题的哈希表法同样适用于本题，但是没有利用到数组有序的条件，非最优，时间复杂度为O(n)。代码如下：

class Solution {

public:

    vector<int> twoSum(vector<int>& numbers, int target) {

		// 哈希表

        map<int, int> hashMap;

        vector<int> ans;

        int temp = 0;

        for (int i = 0; i < numbers.size(); i++)

        {

            temp = target - numbers[i];

            if (hashMap.count(temp))

            {

                ans = { ++hashMap[temp], ++i };

                break;

            }

            hashMap[numbers[i]] = i;

        }

        return ans;

    }

};

2.3 二分法

遍历一个，查找另一个，而数组又是有序的，很容易想到二分法，时间复杂度为O(\(nlogn\))。具体代码如下：

class Solution {

public:

    vector<int> twoSum(vector<int>& numbers, int target) {

		//二分法

        vector<int> result;

        for (int i = 0; i < numbers.size() - 1; i++)

        {

            int second = target - numbers[i];

            int left = i + 1;

            int right = numbers.size() - 1;

            while (left <= right)

            {

                int mid = (left + right) / 2;

                if (second < numbers[mid])

                    right = mid - 1;

                else if (second > numbers[mid])

                    left = mid + 1;

                else

                {

                    result.push_back(++i);

                    result.push_back(++mid);

                    break;

                }

                if (result.size() == 2)

                    break;

            }

        }

        return result;

    }

};

2.4 头尾指针法

该方法特别秒，利用两个指针分别指向头尾，通过头尾数之和和目标数进行比较，前者大则尾指针左移，前者小则指针右移。充分利用了排好序数组这一特性，时间复杂度为O(n),代码如下：

public:

    vector<int> twoSum(vector<int>& numbers, int target) {

        vector<int> result;

        int head = 0;

        int tail = numbers.size() - 1;

        while (head < tail)

        {

            int tempAdd = numbers[head] + numbers[tail];

            if (tempAdd < target)

                head++;

            else if (tempAdd > target)

                tail--;

            else

            {

                result = { ++head, ++tail };

                break;

            }

        }

        return result;

    }

};

参考：https://www.jianshu.com/p/f3a8a247f4c8

巴特西

Leetcode No.167 Two Sum II - Input array is sorted(c++实现）