ゼロから始めるLeetCode Day87 「 1512. Number of Good Pairs」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day86 「33. Search in Rotated Sorted Array」

次回
ゼロから始めるLeetCode Day88「139. Word Break」

Twitterやってます。

問題

1512. Number of Good Pairs
難易度はEasy。

問題としては、整数の配列numsが与えられます。

nums[i] == nums[j] で i < j の場合，ペア(i,j)を有効とし、有効であるペアの数を返すアルゴリズムを設計してください。

Example 1:

Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.

Example 2:

Input: nums = [1,1,1,1]
Output: 6
Explanation: Each pair in the array are good.

Example 3:

Input: nums = [1,2,3]
Output: 0

解法

class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        ans,dic = 0,{}
        for i,j in enumerate(nums):
            if j in dic:
                ans += dic[j]
                dic[j] += 1
            else:
                dic[j] = 1
        return ans
# Runtime: 32 ms, faster than 100.00% of Python3 online submissions for Number of Good Pairs.
# Memory Usage: 13.6 MB, less than 100.00% of Python3 online submissions for Number of Good Pairs.

dicで要素を管理して、はい終わり！
速度や容量的にもかなりいいものがかけたのではないでしょうか（自画自賛）。
急いで書いたので深い解説、とまではいきませんが他にもCounterを使ったり、pointerを二つ使って書いたりもできるとは思います。
その解答をかけるようであれば、ぜひdisucussに投稿してみてください。

では今回はここまで。
お疲れ様でした。