點擊上方藍(lán)字設(shè)為星標(biāo)

下面開始今天的學(xué)習(xí)～

力扣?167.兩數(shù)之和 II - 輸入有序數(shù)組(點擊文末閱讀原文查看題目)題目描述

給定一個已按照?升序排列?的有序數(shù)組，找到兩個數(shù)使得它們相加之和等于目標(biāo)數(shù)。

函數(shù)應(yīng)該返回這兩個下標(biāo)值 index1 和 index2，其中 index1 必須小于 index2。

說明:

• 返回的下標(biāo)值(index1 和 index2)不是從零開始的。
• 你可以假設(shè)每個輸入只對應(yīng)唯一的答案，而且你不可以重復(fù)使用相同的元素。

示例:

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

方法 1：雙指針

算法我們可以使用 力扣 1.兩數(shù)之和的解法在 O(n^2)?時間 O(1)?空間暴力解決，也可以用哈希表在 O(n)?時間和 O(n)?空間內(nèi)解決。然而，這兩種方法都沒有用到輸入數(shù)組已經(jīng)排序的性質(zhì)，我們可以做得更好。我們使用兩個指針，初始分別位于第一個元素和最后一個元素位置，比較這兩個元素之和與目標(biāo)值的大小。如果和等于目標(biāo)值，我們發(fā)現(xiàn)了這個唯一解。如果比目標(biāo)值小，我們將較小元素指針增加一。如果比目標(biāo)值大，我們將較大指針減小一。移動指針后重復(fù)上述比較知道找到答案。

假設(shè)?[...，a，b，c，...，d，e，f，...]?是已經(jīng)升序排列的輸入數(shù)組，并且元素 b，e 是唯一解。因為我們從左到右移動較小指針，從右到左移動較大指針，總有某個時刻存在一個指針移動到 b 或 e 的位置。不妨假設(shè)小指針縣移動到了元素 b，這是兩個元素的和一定比目標(biāo)值大，根據(jù)我們的算法，我們會向左移動較大指針直至獲得結(jié)果。

C++ 代碼實現(xiàn)

class Solution {public: vector<int> twoSum(vector<int>& numbers, int target) { int low = 0, high = numbers.size() - 1; while (low < high) { int sum = numbers[low] + numbers[high]; if (sum == target) return {low + 1, high + 1}; else if (sum < target) ++low; else --high; } return {-1, -1}; }};是否需要考慮 numbers[low] + numbers[high]?溢出呢？答案是不需要。因為即使兩個元素之和溢出了，因為只存在唯一解，所以一定會先訪問到答案。復(fù)雜度分析

時間復(fù)雜度：O(n)。每個元素最多被訪問一次，共有 n 個元素。

空間復(fù)雜度：O(1)。只是用了兩個指針。

本文作者：力扣

編輯&版式：霍霍

聲明：本文歸“力扣”版權(quán)所有，如需轉(zhuǎn)載請聯(lián)系。

點個在看，少個?bug?

總結(jié)

以上是生活随笔為你收集整理的c++两个数组对比去掉重复的元素_LeetCode 题解 | 167.两数之和 II 输入有序数组...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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