Manjusaka

10-03 leetcode 1512

链接 1512. Number of Good Pairs

题目

Given an array of integers nums, return the number of good pairs.

A pair (i, j) is called good if nums[i] == nums[j] and i < j.

题解

这题 N^2 也能过

class Solution:
    def numIdenticalPairs(self, nums: list[int]) -> int:
        count = 0
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                count += nums[i] == nums[j]
        return count

然后优化一下的话，就是用 hash 表记录一下之前出现的频率就行

from collections import defaultdict


class Solution:
    def numIdenticalPairs(self, nums: list[int]) -> int:
        count = 0
        seen = defaultdict(int)
        for num in nums:
            count += seen[num]
            seen[num] += 1
        return count