一道算法优化题，求有序数组是否存在两数之和等于第三个给定的数字

Question

1.题：给出一个函数，判断在一个给定的有序数组中，是否存在两个数之和等于给定的第三个数。

这道题本身挺简单，但是如果直接使用嵌套两个 for 循环的方式去做的话，时间复杂度非常之高。

希望能有大牛给出一个简单的算法优化思路。

Answer 1

经典的two sum problem，保存双指针，分别指向数组开头和末尾，假设数组非降序排列，分情况讨论：

1. 如果当前两个数的和等于给定值，成功。

2. 如果当前两个数的和小于给定值，头指针右移。

3. 如果当前两个数的和大于给定值，尾指针左移。

如果尾指针跑到了头指针左边则无解。

时间复杂度O(N)

也有其他解法，还有3 / 4 sum problem，很容易搜到。

参考：
http://stackoverflow.com/questions/11928091/linear-time-algorithm-for-2-sum
https://leetcode.com/problems/two-sum/

Answer 2

给一个具体实现吧：

function twoSum (arr, sum) {
    var head = 0,
        len = arr.length,
        rear = len - 1,
        sort = arr[head] > arr[rear] ? "down" : "top",
        grade = {
            down: {
                sub: function () {
                    head++;
                },
                add: function () {
                    rear--;
                }
            },
            top: {
                sub: function () {
                    rear--;
                },
                add: function () {
                    head++;
                }
            }
        };
    while (head < rear) {
        if (arr[head] + arr[rear] === sum) {
            return [arr[head], arr[rear]];
        } else if (arr[head] + arr[rear] <= sum) {
            grade[sort].add();
        } else if (arr[head] + arr[rear] >= sum) {
            grade[sort].sub();
        }
    }
    return "该数组中没有满足要求的两个数字";
}