167.給你一個(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í)的額外空間。

#這道題可以使用O（n^2)的時(shí)間復(fù)雜度和O(1)的空間復(fù)雜度暴力求解，或者借助哈希表使用O(n)的時(shí)間復(fù)雜度和 O(n)的空間復(fù)雜度求解。

#但是這兩種解法都是針對(duì)無序數(shù)組的，沒有利用到輸入數(shù)組有序的性質(zhì)。利用輸入數(shù)組有序的性質(zhì)，可以得到時(shí)間復(fù)雜度和空間復(fù)雜度更優(yōu)的解法。


#解答一

class Solution(object): ? ?

????def twoSum(self, numbers, target): ? ? ? ?

????????""" ? ? ? ?

????????:type numbers: List[int] ? ? ? ?

????????:type target: int ? ? ? ?

????????:rtype: List[int] ? ? ? ?

????????""" ? ? ? ?

????????d={} ? ? ? ?

????????for i in range(1,len(numbers)+1): ? ? ? ? ? ?

????????????if target-numbers[i-1] in d: ? ? ? ? ? ? ? ?

????????????????return [d[target-numbers[i-1]],i] ? ? ? ?

????????????else: ? ? ? ? ? ? ? ?

????????????????d[numbers[i-1]]=i

#解答二：二分查找#在數(shù)組中找到兩個(gè)數(shù)，使得它們的和等于目標(biāo)值，可以首先固定第一個(gè)數(shù)，然后尋找第二個(gè)數(shù)，第二個(gè)數(shù)等于目標(biāo)值減去第一個(gè)數(shù)的差。利用數(shù)組的有序性質(zhì)，可以通過二分查找的方法尋找第二個(gè)數(shù)。為了避免重復(fù)，在尋找第二個(gè)數(shù)時(shí)，只在第一個(gè)數(shù)的右側(cè)尋找。

class Solution: ? ?

????def twoSum(self, numbers: List[int], target: int) -> List[int]: ? ? ? ?????????n = len(numbers)? ? ? ??

?????????for i in range(n): ? ? ? ? ? ?

? ? ? ? ? ? ????low, high = i + 1, n - 1 ? ? ? ? ? ?

????????????? while low <= high: ? ? ? ? ? ? ? ?

????????????????mid = (low + high) // 2 ? ? ? ? ? ? ? ?

????????????????if numbers[mid] == target - numbers[i]: ? ? ? ? ? ? ? ? ? ??????????return [i + 1, mid + 1] ? ? ? ? ? ? ? ????????????????elif numbers[mid] > target - numbers[i]: ? ? ? ? ? ? ? ? ? ??????????high = mid - 1 ? ? ? ? ? ? ? ?

????????????????else: ? ? ? ? ? ? ? ? ? ?

????????????????? ? low = mid + 1 ????????????????????? return?[-1,?-1]

#時(shí)間復(fù)雜度：O(nlogn)

#空間復(fù)雜度：O(1)




#解答三:雙指針

#初始時(shí)兩個(gè)指針分別指向第一個(gè)元素位置和最后一個(gè)元素的位置。

#每次計(jì)算兩個(gè)指針指向的兩個(gè)元素之和，并和目標(biāo)值比較。

#如果兩個(gè)元素之和等于目標(biāo)值，則發(fā)現(xiàn)了唯一解。

#如果兩個(gè)元素之和小于目標(biāo)值，則將左側(cè)指針右移一位。

#如果兩個(gè)元素之和大于目標(biāo)值，則將右側(cè)指針左移一位。

#移動(dòng)指針之后，重復(fù)上述操作，直到找到答案。

#使用雙指針的實(shí)質(zhì)是縮小查找范圍。

#那么會(huì)不會(huì)把可能的解過濾掉？答案是不會(huì)。

#假設(shè) numbers[i]+numbers[j]=target 是唯一解，其中0≤i<j≤numbers.length?1。

#初始時(shí)兩個(gè)指針分別指向下標(biāo)?0?和下標(biāo) numbers.length?1，左指針指向的下標(biāo)小于或等于 i，右指針指向的下標(biāo)大于或等于 j。

#除非初始時(shí)左指針和右指針已經(jīng)位于下標(biāo) i 和 j，否則一定是左指針先到達(dá)下標(biāo) i 的位置或者右指針先到達(dá)下標(biāo) j 的位置。

#如果左指針先到達(dá)下標(biāo) i 的位置，此時(shí)右指針還在下標(biāo) j 的右側(cè)，sum>target，因此一定是右指針左移，左指針不可能移到 i 的右側(cè)。#如果右指針先到達(dá)下標(biāo)?j?的位置，此時(shí)左指針還在下標(biāo)?i?的左側(cè)，

#sum<target，因此一定是左指針右移，右指針不可能移到 j 的左側(cè)。

#由此可見，在整個(gè)移動(dòng)過程中，左指針不可能移到 i 的右側(cè)，右指針不可能移到 j 的左側(cè)，因此不會(huì)把可能的解過濾掉。

#由于題目確保有唯一的答案，因此使用雙指針一定可以找到答案。

class Solution: ? ?

????def twoSum(self, numbers: List[int], target: int) -> List[int]: ? ??

????????low, high = 0, len(numbers) - 1 ? ? ? ?

????????while low < high:? ? ? ? ? ?

????????????total = numbers[low] + numbers[high] ? ? ? ? ? ?

????????????if total == target: ? ? ? ? ? ? ? ?

????????????????return [low + 1, high + 1] ? ? ? ? ? ?

????????????elif total < target: ? ? ? ? ? ? ? ?

????????????????low += 1? ? ? ? ? ??

????????????else: ? ? ? ? ? ? ? ?

????????????????high -= 1

????????????????return?[-1,?-1]

C++:

class Solution {

public: ? ?

????vector<int> twoSum(vector<int>& numbers, int target) { ? ? ? ?

????????int i=0; ? ? ? ?

????????int j=numbers.size()-1; ? ? ? ?

????????while (i<j){ ? ? ? ? ? ?

????????????int sum=numbers[i]+numbers[j]; ? ? ? ? ? ?

????????????if (sum<target){ ? ? ? ? ? ? ? ?

????????????????i++; ? ? ? ? ? ?

????????????}else if (sum>target){ ? ? ? ? ? ? ? ?

????????????????j--; ? ? ? ? ? ?

????????????}else{ ? ? ? ? ? ? ? ?

????????????????return vector<int>{i+1,j+1}; ? ? ? ? ? ?

????????????} ? ? ? ?

????????} ? ? ? ?

????return vector<int>{-1,-1}; ? ?????

}};

題目來源：https://leetcode.cn/