【題目描述】
給定一個已按照升序排列 的有序數(shù)組程储，找到兩個數(shù)使得它們相加之和等于目標數(shù)久脯。
函數(shù)應該返回這兩個下標值 index1 和 index2荒辕，其中 index1 必須小于 index2兼搏。
【說明】
1症虑、返回的下標值（index1 和 index2）不是從零開始的。
2勇皇、你可以假設每個輸入只對應唯一的答案罩句，而且你不可以重復使用相同的元素。
【示例】
輸入: numbers = [2, 7, 11, 15], target = 9
輸出: [1,2]
解釋: 2 與 7 之和等于目標數(shù) 9 敛摘。因此 index1 = 1, index2 = 2 的止。
【思路1】
1、暴力解
2着撩、時間復雜度O(n^2)
3、空間復雜度O(n)
4匾委、代碼略
【思路2】
1拖叙、使用哈希表
2、只不過 返回值是排序的
3赂乐、時間復雜度O(n)
4薯鳍、空間復雜度O(n)
Swift 代碼實現(xiàn)：
func twoSum1(_ numbers: [Int], _ target: Int) -> [Int] {
var map = [Int:Int]()
for (i,num) in numbers.enumerated() {
if let index = map[target-num] {
if index > i {
return [i+1,index]
}
return [index,i+1]
}
map[num] = i+1
}
return []
}
【思路3】為啥老想不到雙指針呢！！挖滤！
1崩溪、使用雙指針
2、一個指針指向index=0斩松，另外一個指針指向nums.count-1,也就是一個頭一個尾
3伶唯、因為數(shù)組是有序的且只存在一個答案，所以在頭指針<尾指針遍歷內 就可以找到答案
4惧盹、如果nums[front]+nums[tail] = target ,那么返回index就可以了
5乳幸、如果相加之和大于target，那說明尾指針需要前移钧椰，反之頭指針需要后移粹断，數(shù)組是有序的
6、時間復雜度O(n)
7嫡霞、空間復雜度O(1)
Swift代碼實現(xiàn)：
func twoSum1(_ numbers: [Int], _ target: Int) -> [Int] {
var front = 0
var tail = numbers.count-1
while front < tail {
if numbers[front]+numbers[tail] == target {
return [front+1,tail+1]
}
if numbers[front]+numbers[tail] < target {
front+=1
} else {
tail-=1
}
}
return []
}
