[LeetCode] 167.Two Sum II - Input array is sorted 兩數(shù)之和之二 - 輸入數(shù)組有序

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. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

這又是一道Two Sum的衍生題，作為LeetCode開山之題，我們務(wù)必要把Two Sum及其所有的衍生題都拿下，這道題其實(shí)應(yīng)該更容易一些，因?yàn)榻o定的數(shù)組是有序的，而且題目中限定了一定會(huì)有解，我最開始想到的方法是二分法來搜索，因?yàn)橐欢ㄓ薪猓覕?shù)組是有序的，那么第一個(gè)數(shù)字肯定要小于目標(biāo)值target，那么我們每次用二分法來搜索target - numbers[i]即可，代碼如下：

解法一：

// O(nlgn)
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        for (int i = 0; i < numbers.size(); ++i) {
            int t = target - numbers[i], left = i + 1, right = numbers.size();
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (numbers[mid] == t) return {i + 1, mid + 1};
                else if (numbers[mid] < t) left = mid + 1;
                else right = mid;
            }
        }
        return {};
    }
};

但是上面那種方法并不efficient，時(shí)間復(fù)雜度是O(nlgn)，我們?cè)賮砜匆环NO(n)的解法，我們只需要兩個(gè)指針，一個(gè)指向開頭，一個(gè)指向末尾，然后向中間遍歷，如果指向的兩個(gè)數(shù)相加正好等于target的話，直接返回兩個(gè)指針的位置即可，若小于target，左指針右移一位，若大于target，右指針左移一位，以此類推直至兩個(gè)指針相遇停止，參見代碼如下：

解法二：

// O(n)
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int l = 0, r = numbers.size() - 1;
        while (l < r) {
            int sum = numbers[l] + numbers[r];
            if (sum == target) return {l + 1, r + 1};
            else if (sum < target) ++l;
            else --r;
        }
        return {};
    }
};

類似題目：

Two Sum III - Data structure design

Two Sum

參考資料：

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(167.兩數(shù)之和之二 - 輸入數(shù)組有序)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)兩數(shù)之和之二 - 輸入數(shù)組有序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論