目錄

167.?兩數(shù)之和 II - 輸入有序數(shù)組

題目描述：

實(shí)現(xiàn)代碼與解析：

暴力（超時(shí)）

雙指針

原理思路：

二分

原理思路：

167.?兩數(shù)之和 II - 輸入有序數(shù)組

題目描述：

????????給你一個(gè)下標(biāo)從?1?開始的整數(shù)數(shù)組?numbers?，該數(shù)組已按?非遞減順序排列??，請(qǐng)你從數(shù)組中找出滿足相加之和等于目標(biāo)數(shù)?target?的兩個(gè)數(shù)。如果設(shè)這兩個(gè)數(shù)分別是?numbers[index1]?和?numbers[index2]?，則?1 <= index1 < index2 <= numbers.length?。

以長(zhǎng)度為 2 的整數(shù)數(shù)組?[index1, index2]?的形式返回這兩個(gè)整數(shù)的下標(biāo)?index1?和?index2。

你可以假設(shè)每個(gè)輸入?只對(duì)應(yīng)唯一的答案?，而且你?不可以?重復(fù)使用相同的元素。

你所設(shè)計(jì)的解決方案必須只使用常量級(jí)的額外空間。

示例 1：

輸入：numbers = [2,7,11,15], target = 9
輸出：[1,2]
解釋：2 與 7 之和等于目標(biāo)數(shù) 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

示例 2：

輸入：numbers = [2,3,4], target = 6
輸出：[1,3]
解釋：2 與 4 之和等于目標(biāo)數(shù) 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。

示例 3：

輸入：numbers = [-1,0], target = -1
輸出：[1,2]
解釋：-1 與 0 之和等于目標(biāo)數(shù) -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

實(shí)現(xiàn)代碼與解析：

暴力（超時(shí)）

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> res(2);
        for (int i = 0; i < numbers.size(); i++)
        {
            if (numbers[i] > target / 2 + 1) break;
            for (int j = i + 1; j < numbers.size(); j++)
                {
                    if (numbers[i] + numbers[j] == target)
                    {
                        res[0] = i + 1;
                        res[1] = j + 1;
                    }
                }
        }
        return res;
    }
};

?顯然我們沒(méi)有用到有序的這個(gè)性質(zhì)。

雙指針

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int i = 0, j = numbers.size() - 1;
        while(i < j)
        {
            if (numbers[i] + numbers[j] > target) j--;
            else if (numbers[i] + numbers[j] < target) i++;
            else 
            {
                return {i + 1, j + 1};
            }
        }
        return {};
    }
};

原理思路：

? ? ? ? 根據(jù)有序的性質(zhì)，numbers[i] + numbers[j] > target 說(shuō)明和大了，我們固定左端，右端向左移動(dòng)讓和變小。numbers[i] + numbers[j] <?target 說(shuō)明和小了，我們固定右端，左端向右移動(dòng)讓和變大。

二分

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {

        for (int i = 0; i < numbers.size(); i++)
        {
            int l = i + 1;
            int r = numbers.size() - 1;
            while(l <= r)
            {
                int mid = ((r - l) >> 1) + l;
                if (numbers[mid] > target - numbers[i]) r = mid - 1;
                else if (numbers[mid] < target - numbers[i]) l = mid + 1;
                else return {i + 1, mid + 1};
            }
        }
        return {};
    }
};

原理思路：

? ? ? ? 固定一端，然后二分查找另一段，二分比較簡(jiǎn)單，就不再解釋了。

Leetcode：704. 二分查找（C++）_Cosmoshhhyyy的博客-CSDN博客文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-538679.html

到了這里，關(guān)于Leetcode每日一題：167. 兩數(shù)之和 II - 輸入有序數(shù)組（2023.7.8 C++）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！