課題
問題：
与えられた整数の配列**
numsと整数targetに対して、その和がtargetになるような2つの数のインデックスを返します。各入力には正確に1つの解**が存在し、同じ要素を2回使うことはできません。答えは任意の順序で返して構いません。
例 1:
入力: nums = [2,7,11,15]、ターゲット = 9
出力: [0,1]
説明: nums[0] + nums[1] == 9 であるため、[0, 1] を返します。
例 2:
入力:数値 = [3,2,4]、ターゲット = 6
出力: [1,2]
例 3:
入力:数値 = [3,3]、ターゲット = 6
出力: [0,1]
制約:
2 <= nums.length <= 104109 <= nums[i] <= 109109 <= target <= 109
フォローアップ: 時間の計算量よりも少ないアルゴリズムを思いつくことはできますか?O(n2)
point
今回は、O(n)、すなわち「ビッグオー記法」と呼ばれる計算複雑性を表す記法を学ぶことができる問題になっています。
計算機科学において、アルゴリズムの実行時間や、リソース使用量の増加率を記述するために使用されます。O(n)は、アルゴリズムの実行時間が入力サイズnに対して線形に増加することを意味しています。
つまり！入力サイズが２倍になると、実行時間も２倍になる！ということです。
ビッグオー記法には他にも、O(1)(定数時間)、O(log n)(対数時間)、O(n^2)(二乗時間)などがあります。それぞれ、アルゴリズムの実行時間が入力サイズに対して、どのようなスケールをするかみてみましょう。
・O(1)(定数時間)：入力サイズに関わらず実行時間が変わらないこと。
・O(log n)(対数時間)：実行時間が入力サイズの対数に比例して増加すること。
・O(n^2)(二乗時間)：実行時間が入力サイズの平方に比例して増加すること。
ただコードが書けるだけではなく、以下に効率よく品質の高いコードが書けるかが重要になってきます。その際に用いられるのが上記のようなpointです。（奥が深いですね。。）
では、早速解いていきましょう。
まず悪い例から！
class Solution {
public int[] twoSum(int[] nums, int target) {
int num = 0;
int num2 = 0;
int gokei = 0;
int[] values = new int[2];
for (int i = 0; i < nums.length; i ++){
num = nums[i];
for(int u = i + 1; u < nums.length; u ++ ){
num2 = nums[u];
gokei = num + num2;
if(gokei == target){
values[0] = i;
values[1] = u;
return values;
}
}
}
return values;
}
}
上記のコードは無駄な点が多すぎますね。。
いくつかの観点から、何がダメなのか見ていきましょう！
機能性
- この関数は、与えられた**
nums配列とtargetから、2つの数の和がtarget**になるようなインデックスのペアを見つけ出すという問題の基本的な要件を満たしています。そのため、機能性の観点では基本的な要件を満たしていると言えます。
効率性
- 時間複雑度はO(n^2)です。これは2重のforループによるもので、入力サイズが大きくなるとパフォーマンスが著しく低下します。より効率的なアルゴリズム（例えば、ハッシュマップを使用したO(n)の解法）が存在するため、効率性の観点では改善の余地があります。
可読性
- 変数の命名は一部改善の余地があります。例えば、**
numやnum2**よりも、意味を持つ名前を使用することでコードの可読性を高めることができます。しかし、全体としてはシンプルで理解しやすいコードになっています。
改善の余地
- 効率性を向上させるためにハッシュマップを利用するなど、アルゴリズムを改善できます。
- コーディング規約に従った変数名を利用することで可読性を向上させることが可能です。
あえて点数をつけるなら。。。
- 機能性: 8/10 - 基本的な要件は満たしていますが、全てのケースで最適な解を提供しているわけではありません。
- 効率性: 4/10 - O(n^2)の時間複雑度は、大きなデータセットでは非効率です。
- 可読性: 7/10 - コードは比較的シンプルで読みやすいですが、変数名がより具体的であれば理解しやすくなります。
とりあえず、動けばいいという感じでしょうか。。
では、正しい例を見てみましょう！
class Solution {
public int[] twoSum(int[] nums, int target) {
// 数値とそのインデックスを保持するハッシュマップを用意
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
// 現在の数値に対して、目標値から引いた残りの数値がマップに存在するかを確認
int complement = target - nums[i];
if (map.containsKey(complement)) {
// 補数が見つかった場合は、現在のインデックスとマップ内の補数のインデックスを返す
return new int[] { map.get(complement), i };
}
// 現在の数値とそのインデックスをマップに追加
map.put(nums[i], i);
}
// 解が必ず存在すると仮定しているため、ここに到達することはない。
// しかし、メソッドが常にint[]を返すようにするため、
// 解が見つからない場合の例外を投げる。
throw new IllegalArgumentException("No two sum solution");
}
}
ハッシュマップを使うことで、各数値の補数をO(1)の時間複雑度で検索できるため、全体のアルゴリズムの時間複雑度はO(n)になります。これは、2重ループを使った直接的なアプローチ（O(n^2)の時間複雑度）よりも大幅に効率的です。
コードの特に複雑な部分の解説
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
例えば、nums = {1,3,5,7} target = 8だとします。
1回目のループ
i = 0の時、nums[i] = 1complement = 8 - 1 = 7mapは空なので、complementがmapに存在するかのチェックはfalse- **
map.put(1, 0)が実行され、mapには{1: 0}**が追加されます
2回目のループ
i = 1の時、nums[i] = 3complement = 8 - 3 = 5mapには{1: 0}が含まれているのみなので、complementがmapに存在するかのチェックは再びfalse- **
map.put(3, 1)が実行され、mapには{1: 0, 3: 1}**が追加されます
3回目のループ
i = 2の時、nums[i] = 5complement = 8 - 5 = 3- この時点で**
mapには{1: 0, 3: 1}が含まれており、complementの値3がmapに存在します。これは、nums[2]（値は5）とnums[1]（値は3）が合計してtarget**の8になることを意味します。 - 条件が**
trueになり、map.get(complement)は1を返します。これはcomplement**（3）のインデックスです。 - したがって、**
return new int[] { map.get(complement), i };はreturn new int[] { 1, 2 };**を実行します。
結果
この例では、nums[1]（値は3）と**nums[2]（値は5）が合計して8になるので、そのインデックスの配列{1, 2}**が返されます。
以上。
アルゴリズムを考えてコード書くことは、難しいですね。。