[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及其所有的衍生題都拿下，這道題其實應(yīng)該更容易一些，因為給定的數(shù)組是有序的，而且題目中限定了一定會有解，我最開始想到的方法是二分法來搜索，因為一定有解，而且數(shù)組是有序的，那么第一個數(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，時間復(fù)雜度是O(nlgn)，我們再來看一種O(n)的解法，我們只需要兩個指針，一個指向開頭，一個指向末尾，然后向中間遍歷，如果指向的兩個數(shù)相加正好等于target的話，直接返回兩個指針的位置即可，若小于target，左指針右移一位，若大于target，右指針左移一位，以此類推直至兩個指針相遇停止，參見代碼如下：

解法二：

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

最新評論