Algorithem_TwoPointers#
Two Sum II - Input Array Is Sorted#
Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.
Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.
The tests are generated such that there is exactly one solution. You may not use the same element twice.
Your solution must use only constant extra space.
Example 1:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
Example 2:
Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].
Example 3:
Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].
解法一#
直接遍历，双重 for 循环，但是 i != j
代码如下：
class Solution {
func twoSum(_ numbers: [Int], _ target: Int) -> [Int] {
var indexList: [Int] = []
for i in 0..<numbers.count {
for j in (i+1)..<numbers.count {
if numbers[i] + numbers[j] == target {
indexList.append(i+1)
indexList.append(j+1)
break
}
}
if indexList.count > 0 {
break
}
}
return indexList
}
}
但是上面的没有算法可言，故而，需要优化，由于数组是有序的，所以，index=0 的地方是最小的，index=count-1 的地方是最大的，使用 TwoPointer 的解法，应该是定义两个变量，从头和尾一起开始，头 + 尾 > target，尾变小往前移，头 + 尾 < target，头变大往后移，头 + 尾等于结果，则返回
代码如下：
class Solution {
func twoSum(_ numbers: [Int], _ target: Int) -> [Int] {
var i = 0;
var j = numbers.count - 1;
while (i < j) {
let small = numbers[i]
let big = numbers[j]
if small + big == target {
break
}
else if small + big < target {
i += 1
}
else {
j -= 1
}
}
return [i+1, j+1]
}
}
解法二#
这种解法是借助字典的功能，字典的 key 是数组的值，value 是数组的 index，然后遍历数组，如果发现 target-num 的值在字典里，则返回 [dic [target-num] + 1, index]，如果不在字典里，则存储 {num: index} 到字典中。由于是数组有序，从小到大遍历，所以最终找到结果时返回顺序字典中 value 对应的 index 是小的，所以在第一个
代码如下：
class Solution {
func twoSum(_ numbers: [Int], _ target: Int) -> [Int] {
var dic: [Int: Int] = [:]
for index in 0..<numbers.count {
let num = numbers[index]
if dic.keys.contains(target-num) {
return [dic[target-num]! + 1, index+1]
}
else {
dic[num] = index
}
}
return []
}
}
解法三#
这种解法是使用 BinarySearch 解法，逻辑是，遍历数组，每次遍历得到 target 和当前数字的差值，然后需要做的是，在数组之后的元素中查找有没有这个差值；有则返回对应的 index，没有则继续下一次遍历
代码如下：
class Solution {
func twoSum(_ numbers: [Int], _ target: Int) -> [Int] {
for i in 0..<numbers.count {
let num = numbers[i]
let tmp = target - num
// 然后使用 binarySearch 查找有没有等于 tmp 的元素
var l = i + 1
var r = numbers.count - 1
var middle = 0
while (l <= r) {
middle = l + (r - l) / 2
if numbers[middle] == tmp {
return [i+1, middle+1]
}
else if numbers[middle] < tmp {
l += 1
}
else {
r -= 1
}
}
}
return []
}
}