DailyChallenge

第167回 2つの数の和II - 入力順序配列

イージー20200720

説明

昇順に並べ替えられた配列が与えられたとき、その和が目的の数に等しい2つの数を求めなさい。

この関数は、2 つの添え字 index1 と index2 を返す必要があります。

説明

"

• 返される添え字の値は、0 から始まりません。
• 各入力は一意の答えにのみ対応し、同じ要素を再利用することはできないと仮定できます。

 :
 : numbers = [2, 7, 11, 15], target = 9
 : [1,2]
 : 2 と7の和は目標数9に等しい したがって、index1= 1, index2 = 2 。

Solution

1. 二分探索

まず最初の数字を確定し、次に2番目の数字を探します。

最初の数字は、小さいものから大きいものへと反復して求めることができます。

番目の数字は、大きいものから小さいものへと二等分されます。しかし、最適化があります。2番目の数値は、前のループでターゲットが見つからなかったときにループから飛び出したループの中盤より大きくなることはないため、2番目の数値の範囲は[i + 1, mid(前のループの中盤)]となります。

class Solution {
 public int[] twoSum(int[] numbers, int target) {
 int n = numbers.length;
 int index = n - 1;
 for (int i = 0; i < numbers.length; ++i) {
 int low = i + 1, high = index;
 while (low <= high) {
 int mid = (high - low) / 2 + low;
 if (numbers[mid] == target - numbers[i]) {
 return new int[]{i + 1, mid + 1};
 } else if (numbers[mid] > target - numbers[i]) {
 high = mid - 1;
 } else {
 low = mid + 1;
 }
 index = mid;
 }
 }
 return new int[]{-1, -1};
 }
}

1. ダブルポインタ

質問で言われていることは存在するはずで、コードを見て体験すれば理解できるはずです。

class Solution {
 public int[] twoSum(int[] numbers, int target) {
 int low = 0, high = numbers.length - 1;
 while (low < high) {
 int sum = numbers[low] + numbers[high];
 if (sum == target) {
 return new int[]{low + 1, high + 1};
 } else if (sum < target) {
 ++low;
 } else {
 --high;
 }
 }
 return new int[]{-1, -1};
 }
}

TODO:動的計画法のトピックス