Algorithem_TwoPointers#
Two Sum II - Input Array Is Sorted#
1-indexed の整数配列 numbers が非減少順にソートされているとき、2 つの数値を見つけて、それらが特定の目標数値に合計されるようにします。これらの 2 つの数値を numbers [index1] と numbers [index2] とし、1 <= index1 < index2 <= numbers.length とします。
整数配列 [index1, index2] のインデックスを、1 を加えた整数配列 [index1, index2] として返します。
テストはちょうど 1 つの解が生成されるように生成されます。同じ要素を 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 の解法を使用する必要があります。つまり、2 つの変数を定義し、先頭と末尾から同時に開始し、先頭 + 末尾 > 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]
}
}
解法二#
この解法は、辞書の機能を利用しています。辞書のキーは配列の値であり、値は配列のインデックスです。次に、配列を反復処理し、target-num の値が辞書にある場合、[dic [target-num] + 1, index] を返します。辞書にない場合は、{num: 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 と現在の数字の差を取得します。次に、配列の後の要素でこの差が存在するかどうかを検索する必要があります。存在する場合は、対応するインデックスを返し、存在しない場合は次の反復を続けます。
コードは以下の通りです：
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 []
}
}