Algorithem_TwoPointers#
Two Sum II - Input Array Is Sorted#
給定一個已經按非遞減順序排序的從 1 開始索引的整數數組 numbers，找到兩個數字使它們相加等於特定的目標數字。讓這兩個數字分別為 numbers [index1] 和 numbers [index2]，其中 1 <= index1 < index2 <= numbers.length。
將兩個數字的索引 index1 和 index2 加 1 後作為一個長度為 2 的整數數組 [index1, index2] 返回。
測試用例保證只有一個解。不能使用相同的元素兩次。
你的解法必須只使用恆定的額外空間。
示例 1：
輸入：numbers = [2,7,11,15], target = 9
輸出：[1,2]
解釋：2和7的和為9。因此，index1 = 1，index2 = 2。我們返回[1, 2]。
示例 2：
輸入：numbers = [2,3,4], target = 6
輸出：[1,3]
解釋：2和4的和為6。因此，index1 = 1，index2 = 3。我們返回[1, 3]。
示例 3：
輸入：numbers = [-1,0], target = -1
輸出：[1,2]
解釋：-1和0的和為-1。因此，index1 = 1，index2 = 2。我們返回[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 []
}
}