What is the primary pattern used to solve the Maximum Number of Pairs in Array problem?

The primary pattern is array scanning plus hash lookup. You count the frequency of each number and then form pairs based on those frequencies.

How can I optimize my solution for this problem?

Using a hash table to store the frequency of each number allows for efficient counting, and the overall solution can be done in linear time.

What happens if there are no pairs to form?

If no pairs can be formed, the result will be 0 pairs and the array will have all its elements as leftovers.

Can this problem be solved with sorting?

Sorting could work, but it would be less efficient. Using a hash table for counting is typically faster.

What is the space complexity of the solution?

The space complexity is O(k), where k is the number of unique integers in the array, due to the hash table storing frequencies.

#2341

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

数组能形成多少数对

给你一个下标从 0 开始的整数数组 nums 。在一步操作中，你可以执行以下步骤：从 nums 选出两个相等的整数从 nums 中移除这两个整数，形成一个数对请你在 nums 上多次执行此操作直到无法继续执行。返回一个下标从 0 开始、长度为 2 的整数数组 answer 作为答案，…

数组哈希表计数

题目描述

给你一个下标从 0 开始的整数数组 nums 。在一步操作中，你可以执行以下步骤：

从 nums 选出两个 相等的 整数
从 nums 中移除这两个整数，形成一个数对

请你在 nums 上多次执行此操作直到无法继续执行。

返回一个下标从 0 开始、长度为 2 的整数数组 answer 作为答案，其中 answer[0] 是形成的数对数目，answer[1] 是对 nums 尽可能执行上述操作后剩下的整数数目。

示例 1：

输入：nums = [1,3,2,1,3,2,2]
输出：[3,1]
解释：
nums[0] 和 nums[3] 形成一个数对，并从 nums 中移除，nums = [3,2,3,2,2] 。
nums[0] 和 nums[2] 形成一个数对，并从 nums 中移除，nums = [2,2,2] 。
nums[0] 和 nums[1] 形成一个数对，并从 nums 中移除，nums = [2] 。
无法形成更多数对。总共形成 3 个数对，nums 中剩下 1 个数字。

示例 2：

输入：nums = [1,1]
输出：[1,0]
解释：nums[0] 和 nums[1] 形成一个数对，并从 nums 中移除，nums = [] 。
无法形成更多数对。总共形成 1 个数对，nums 中剩下 0 个数字。

示例 3：

输入：nums = [0]
输出：[0,1]
解释：无法形成数对，nums 中剩下 1 个数字。

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 100

lightbulb

解题思路

方法一：计数

我们可以统计数组 $\textit{nums}$ 中每个数字 $x$ 出现的次数，记录在哈希表或数组 $\textit{cnt}$ 中。

然后遍历 $\textit{cnt}$ ，对于每个数字 $x$ ，如果 $x$ 出现的次数 $v$ 大于 $1$ ，则可以从数组中选出两个 $x$ 形成一个数对，我们将 $v$ 除以 $2$ 向下取整，即可得到当前数字 $x$ 可以形成的数对数目，然后我们累加这个数目到变量 $s$ 中。

最后剩余的个数为数组 $\textit{nums}$ 的长度减去可以形成的数对数目乘以 $2$ ，即 $n - s \times 2$ 。

答案为 $[s, n - s \times 2]$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(C)$ 。其中 $n$ 为数组 $\textit{nums}$ 的长度；而 $C$ 为数组 $\textit{nums}$ 中数字的范围，本题中 $C = 101$ 。

1

2

3

4

5

6

class Solution:
    def numberOfPairs(self, nums: List[int]) -> List[int]:
        cnt = Counter(nums)
        s = sum(v // 2 for v in cnt.values())
        return [s, len(nums) - s * 2]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate identify the necessity of counting frequencies to determine pairs?
question_mark
How well does the candidate handle hashing and array scanning in their solution?
question_mark
Is the candidate aware of how to efficiently calculate leftovers after pairing?

warning

常见陷阱

外企场景

error
Overlooking the need to count frequencies before trying to form pairs.
error
Forgetting to account for leftover integers after forming pairs.
error
Not using a hash table or efficient data structure for counting, which leads to poor performance.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the array contains negative numbers?
arrow_right_alt
How would the solution change if duplicates can be paired multiple times?
arrow_right_alt
What if we are asked to find pairs with different conditions, such as pairs whose sum equals a target?

help

常见问题

外企场景

继续练习

#2347 最好的扑克手牌 #2364 统计坏数对的数目 #2284 最多单词数的发件人