アルゴリズム_TwoPointers#
Two Sum II - Input Array Is Sorted#
既に非減少順にソートされた 1 から始まる整数の配列 numbers が与えられ、特定の目標数に合計できる 2 つの数を見つけます。これらの 2 つの数を numbers [index1] と numbers [index2] とし、1 <= index1 < index2 <= numbers.length とします。
長さ 2 の整数配列 [index1、index2] として、2 つの数のインデックス、index1 と index2 を 1 つずつ追加して返します。
テストは正確に 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 つの変数を定義し、先頭と末尾から同時に開始し、head+tail>target の場合、tail を減らして前に移動し、head+tail<target の場合、head を増やして後ろに移動します。head+tail が結果と等しい場合、返します。
コードは以下の通りです：
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 []
}
}