Algorithem_TwoPointers#
Two Sum II - 輸入數組已排序#
給定一個已按非遞減順序排序的 1 索引整數數組 numbers，找到兩個數字，使它們的和等於特定的目標數字。讓這兩個數字為 numbers [index1] 和 numbers [index2]，其中 1 <= index1 < index2 <= numbers.length。
返回這兩個數字的索引，index1 和 index2，加一後作為一個整數數組 [index1, index2]，長度為 2。
測試用例生成的情況下，恰好有一個解。您不能使用同一個元素兩次。
您的解決方案必須僅使用常數額外空間。
範例 1:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: 2 和 7 的和是 9。因此，index1 = 1，index2 = 2。我們返回 [1, 2]。
範例 2:
Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: 2 和 4 的和是 6。因此 index1 = 1，index2 = 3。我們返回 [1, 3]。
範例 3:
Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: -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 []
}
}