【题目描述】
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
【说明】
1、返回的下标值（index1 和 index2）不是从零开始的。
2、你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
【示例】
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 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 代码实现：
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、因为数组是有序的且只存在一个答案，所以在头指针<尾指针遍历内 就可以找到答案
4、如果nums[front]+nums[tail] = target ,那么返回index就可以了
5、如果相加之和大于target，那说明尾指针需要前移，反之头指针需要后移，数组是有序的
6、时间复杂度O(n)
7、空间复杂度O(1)
Swift代码实现：
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 []
}
