はじめに

整数の配列 nums の最大値と最小値を取り出しては平均値を算出し、ユニークな平均値の数を答えよ、というもの。 つまり [4,1,4,0,3,5] であれば、分かりやすく昇順に並べると [0, 1, 3, 4, 4, 5] で、まず [0, 5] の平均値 2.5、そして [1, 4] の平均値 2.5、[3, 4] の平均値 3.5 の 3 つがあります。 2.5 は 2 回登場するため、答えには 1 回だけカウントアップします。よって答えは 2 です。

まずは失敗した手をご覧あれ。

失敗

最初に書いたように、昇順にソートした後前と後ろの値から次々に平均値を算出し、それをハッシュマップに格納します。また、ハッシュマップに格納した回数をカウントすることで答えが導けます。 つまづいたのは、平均として返される float64 の値をどう map に格納するかです。これで行けるかな？と提出したところ 11/36 pass で、原因不明でした。 そこで print 文を埋め込むと期待通り map のキーに格納できていないことが分かり、悩んでいるときに突然頭がすっきりして出てきた答えが次の手です。

https://leetcode.com/problems/number-of-distinct-averages/submissions/1627683780

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func distinctAverages(nums []int) int {
    slices.Sort(nums)
    seen := make(map[string]bool, len(nums))
    ans := 0
    for i := 0; i < len(nums) / 2; i++ {
        avg := string((nums[i] + nums[len(nums) - i - 1]) / 2.0)
        if !seen[avg] {
            ans++
            seen[avg] = true
        }
    }
    return ans
}

成功

平均を取るのをやめ、単に 2 つの値の合計値をハッシュマップに格納する方法にしました。 目的は一意な平均値の数ですが、一意な和の数と捉えても変わりません。 4 つの値をそれぞれ a, b, c, d とし、(a + b) / 2 = (c + d) / 2 が成り立つとき、両辺に 2 をかけると a + b = c + d となるためです。それだけです。

https://leetcode.com/problems/number-of-distinct-averages/submissions/1627853118

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func distinctAverages(nums []int) int {
    slices.Sort(nums)
    seen := make(map[int]bool, len(nums))
    ans := 0
    for i := 0; i < len(nums) / 2; i++ {
        sum := nums[i] + nums[len(nums) - i - 1]
        if !seen[sum] {
            ans++
            seen[sum] = true
        }
    }
    return ans
}

他の回答もキーワードはソート、ハッシュマップ、Two Pointers だったので、これ以上の説明は割愛します。