概要
エンジニア職での就職・転職では会社によってはコーディングテストというものがあります。
新卒でも中途でも入社したい会社というのは誰でもいい環境を求めるのではないでしょうか。
そこで、コーディングテストで振り落とされないためにもLeetCodeというテスト対策ができるサイトでアルゴリズム力を鍛えたいと思います。
問題
整数numsの配列と整数kが与えられたとき、その和がkに等しい部分配列の総数を返す。
部分配列とは、配列内の連続した空でない要素の列のことです。
制約
1 <= nums.length <= 2 * 104-1000 <= nums[i] <= 1000-107 <= k <= 107
解説
初めに合計数の出現回数をカウントするためにDictionary<int,int>を作成します。
この際、初期値として(0, 1) を格納してください。理由は後程説明いたしますが、この値は「合計数0が1回出現した」という意味を表します。
SubarraySum
int sum = 0, ans = 0;
// 合計数の出現回数をカウントするためのDictionaryを作成
var dictionary = new Dictionary<int, int>()
{
// 後の処理のために合計数0を1として初期値を指定する
{0, 1},
};次に、numsから値を一つずつ取り出して、先頭からの合計数を数えていきます。
SubarraySum
// numsから数字を一つずつ取り出す
for (int i = 0; i < nums.Length; i++)
{
// 先頭からの合計値に取り出した数を加算する
sum += nums[i];
}そして、「期待値と合計数の差」が「合計値」として過去に出現したかを確認します。
出現済みだった場合、「過去に出現した箇所」から「現在確認している値の箇所」までが期待値と同じ数になる部分配列になるため、過去に出現した回数を加算します。
SubarraySum
// numsから数字を一つずつ取り出す
for (int i = 0; i < nums.Length; i++)
{
// 先頭からの合計値に取り出した数を加算する
sum += nums[i];
// 期待値と合計値との差の数を合計値として過去に出現したか確認
if (dictionary.ContainsKey(sum - k))
{
// 出現回数を回答に加算する
ans += dictionary[sum - k];
}
}期待値の同じ数になる部分配列かどうかの確認が終えたら、合計値の出現回数を加算していきます。
最後に部分配列の数を返して終了です。
SubarraySum
// numsから数字を一つずつ取り出す
for (int i = 0; i < nums.Length; i++)
{
// 先頭からの合計値に取り出した数を加算する
sum += nums[i];
// 期待値と合計値との差の数を合計値として過去に出現したか確認
if (dictionary.ContainsKey(sum - k))
{
// 出現回数を回答に加算する
ans += dictionary[sum - k];
}
// 合計値の出現回数を加算する
dictionary[sum] = dictionary.GetValueOrDefault(sum) + 1;
}
return ans;ソースコード
Solution.cs
public class Solution {
public int SubarraySum(int[] nums, int k)
{
// 確認した合計値をカウントするためのDictionaryを作成
var dictionary = new Dictionary<int, int>()
{
// 後の処理のために合計数0を1として初期値を指定する
{0, 1},
};
int sum = 0, ans = 0;
// numsから数字を一つずつ取り出す
for (int i = 0; i < nums.Length; i++)
{
// 先頭からの合計値に取り出した数を加算する
sum += nums[i];
// 期待値と合計値との差の数を合計値として過去に出現したか確認
if (dictionary.ContainsKey(sum - k))
{
// 出現回数を回答に加算する
ans += dictionary[sum - k];
}
// 合計値の出現回数を加算する
dictionary[sum] = dictionary.GetValueOrDefault(sum) + 1;
}
return ans;
}
}