【C#】配列から2つの要素を選び、指定した和になる組み合わせを列挙する

はじめに

今回扱ってみる問題はこんな感じ。

n個の配列Aと整数kが入力として与えられたとき，Aの2つの要素の和がkとなる組み合わせを列挙せよ

例.
入力：A = {1, 6, 4, 5, 3}，k = 7
出力：(6, 1), (3, 4)

解き方

まずは2重ループを使った全探索の方法が思いつきましたが、計算量は $o(n^2)$ と性能は良さそうではありません。

少し工夫をしてみると、辞書(ハッシュテーブル)を活用することで計算量 $o(n)$ にまで減らすことができます。

/// <summary>
/// 2つの要素の和がsumになる組み合わせ
/// </summary>
public static IEnumerable<IEnumerable<int>> FindPairs(IReadOnlyList<int> nums, int sum)
{
    var dic = new Dictionary<int, bool>();

    for (int i = 0; i < nums.Count; i++)
    {
        var current = nums[i];
        var couterpart = sum - current;

        if (dic.ContainsKey(couterpart)) yield return new int[] { current, couterpart };
        else dic[current] = true;
    }
}

使い方

ちゃんと動作するか簡単なテストをしてみましょう。

static void Main(string[] args)
{
    var a = new int[] { 1, 6, 4, 5, 3 };
    foreach (var item in FindPairs(a, 7))
        Console.WriteLine(string.Join(", ", item));     // (6, 1), (3, 4)
}