首页 » 编程之美 » 正文

[leetcode]Two Sum II – Input array is sorted

此题我用的是 二分查找,毕竟有序嘛。其实更好的解法,应该是 一个数组,left right下标往里移动查找,这个题我曾经应该在编程之美或者剑指offer上看到过。

class Solution {
public:
    vector&lt;int&gt; result;<br />
    void bSearch(vector&lt;int&gt;&amp;numbers, int start, int end, int find) {
        if (start &gt; end) return;
        int middle = (start + end) / 2;
        if (find == numbers[middle]) {
            result.push_back(middle + 1);
            return ;
        }
        else
            if (find &gt; numbers[middle]) {
                bSearch(numbers, middle+1, end, find);
            }
            else {
                bSearch(numbers, start, middle-1, find);
            }
    }
    vector&lt;int&gt; twoSum(vector&lt;int&gt;&amp; numbers, int target) {
        for (int i = 0; i &lt; numbers.size(); i++) {
            int find = target - numbers[i];
            result.push_back(i + 1);
            bSearch(numbers, i+1, numbers.size(), find);
            if (2 == result.size()) {
                return result;
            }
            result.clear();<br />
        }
        return result;
    }
};

发表评论