給定一個(gè)有序的數(shù)組，和一個(gè)整數(shù)目標(biāo)，求兩個(gè)數(shù)的和等于目標(biāo)的索引，索引從1開始。假設(shè)必定存在解。

有兩種思路：

直接找：

vector<int> twoSum(vector<int>& numbers, int target) {int s = 0, e = numbers.size() - 1;while (true) {if (numbers[s] + numbers[e] > target)e--;else if (numbers[s] + numbers[e] < target)s++;else {return vector<int> {s + 1, e + 1};}}}

原理顯而易見，最壞情況，也就O(n)，當(dāng)兩個(gè)索引位于中間位置。

二分查找：

vector<int> twoSum(vector<int>& numbers, int target) {auto tail = upper_bound(numbers.begin(), numbers.end(), target);auto start = numbers.begin();for (;start != tail;) {int other = target - *start;++start;tail = lower_bound(start, tail, other);if (other == *tail) {vector<int> ret = {start - numbers.begin(), tail - numbers.begin() + 1};return move(ret);}other = target - *tail;--tail;start = lower_bound(start, tail, other);if (other == *start) {vector<int> ret = {start - numbers.begin() + 1, tail - numbers.begin() + 2};return move(ret);}}}

每次都是二分地前進(jìn)后退，最壞情況下達(dá)到O(nlogn)，當(dāng)兩索引位于中間。

但當(dāng)兩個(gè)答案靠近某一端時(shí)性能較好。就leetcode結(jié)果來看，相差不大。

轉(zhuǎn)載于:https://www.cnblogs.com/willaty/p/8376786.html

總結(jié)

以上是生活随笔為你收集整理的leetcode 167 Two Sum II - Input array is sorted的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。