概要
エンジニア職での就職・転職では会社によってはコーディングテストというものがあります。
新卒でも中途でも入社したい会社というのは誰でもいい環境を求めるのではないでしょうか。
そこで、コーディングテストで振り落とされないためにもLeetCodeというテスト対策ができるサイトでアルゴリズム力を鍛えたいと思います。
問題
整数numsの配列と整数targetが与えられたとき、2つの数値の足し算がtargetになるようなインデックスを返す。
各入力にはちょうど1つの解があると仮定してもよいが、同じ要素を2回使ってはいけない。
また、どのような順序で答えを返してもよい。
制約
2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109有効な答えはひとつしかない。
解説
初めに確認済みの値とインデックスを記録するためにDictionary<int, int> を作成して、numsを順番に確認するためのfor文を用意します。
// 確認済みの値とインデックスを記録するためのDictionaryを作成
var dictionary = new Dictionary<int, int>();
// numsの先頭から順に確認
for (int i = 0; i < nums.Length; i++)
{
}次に、合計値をtarget と一致させるためにtargetから取り出した値を引きます。そしてその値を見たかDictionaryを確認します。
この際、Dictionary で確認するのはvalue ではなくkeyとしてください。Dictionary<TKey, TValue> クラスのContainsKey メソッドの計算量はO(1)に近いですが、ContainsValue メソッドはO(n) となるため、入力数が増えると計算量も増加してしまいます。
// numsの先頭から順に確認
for (int i = 0; i < nums.Length; i++)
{
// 合計値をtargetと一致させるために必要な値が確認済みか
if (dictionary.ContainsKey(target - nums[i]))
{
}
}Dictionary に探したい値があれば、インデックスをペアにして返し、なければ値とインデックスをペアにして記憶するためDictionary に追加します。
取り出した値がすでに確認済みの値と重複していれば、「有効な答えはひとつしかない」という制約により答えと違う値ということになりますので、追加せずにスキップします。
最後に見つからなかった場合、空の配列を返すようにして完了です。
// numsの先頭から順に確認
for (int i = 0; i < nums.Length; i++)
{
// 合計値をtargetと一致させるために必要な値が確認済みか
if (dictionary.ContainsKey(target - nums[i]))
{
// インデックスを合わせて返す
return new int[] { dictionary[target - nums[i]] , i};
}
// 確認したことのない値であればDictionaryに追加する
else if (!dictionary.ContainsKey(nums[i]))
{
dictionary.Add(nums[i], i);
}
}
return new int[2];ソースコード
public class Solution {
public int[] TwoSum(int[] nums, int target)
{
// 確認済みの値とインデックスを記録するためのDictionaryを作成
var dictionary = new Dictionary<int, int>();
// numsの先頭から順に確認
for (int i = 0; i < nums.Length; i++)
{
// 合計値をtargetと一致させるために必要な値が確認済みか
if (dictionary.ContainsKey(target - nums[i]))
{
// インデックスを合わせて返す
return new int[] { dictionary[target - nums[i]] , i};
}
// 確認したことのない値であればDictionaryに追加する
else if (!dictionary.ContainsKey(nums[i]))
{
dictionary.Add(nums[i], i);
}
}
return new int[2];
}
}