1.題目
給你一個(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] 河哑。
提示：
2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers 按 非遞減順序 排列
-1000 <= target <= 1000
僅存在一個(gè)有效答案
2.雙指針
初始時(shí)兩個(gè)指針?lè)謩e指向第一個(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ì)把可能的解過(guò)濾掉蒲赂？答案是不會(huì)阱冶。
由于題目確保有唯一的答案，因此使用雙指針一定可以找到答案滥嘴。
3.代碼
object Solution {
def twoSum(numbers: Array[Int], target: Int): Array[Int] = {
var left = 0
var right = numbers.length-1
while (left<right){
if(numbers(left)+numbers(right)==target) {
return Array[Int](left + 1,right+1)
}
else if(numbers(left)+numbers(right)>target){
right = right - 1
}
else {
left=left+1
}
}
Array[Int](-1,-1)
}
}
3.1.復(fù)雜度分析
時(shí)間復(fù)雜度：O(n)木蹬，其中 n 是數(shù)組的長(zhǎng)度。兩個(gè)指針移動(dòng)的總次數(shù)最多為 n 次若皱。
空間復(fù)雜度：O(1)届囚。
