What is the main pattern to solve Check if Array is Good?

The key pattern is array scanning plus hash lookup: find the maximum element, then count occurrences to verify the array matches base[n].

Can this approach handle arrays with length up to 100?

Yes, scanning the array once and using a hash table keeps time and space within acceptable limits for length up to 100.

What if nums contains numbers outside 1 to n?

Any number outside the range 1 to n immediately invalidates the good array pattern, so the function should return false.

Why do we need to check the array length?

The length must be n + 1 to match base[n], so verifying it prevents false positives where elements appear correct but count is insufficient.

Is there a simpler alternative to hash tables?

A counting array can replace a hash table since nums elements are bounded, allowing constant-time access for frequency checks.

#2784

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

检查数组是否是好的

给你一个整数数组 nums ，如果它是数组 base[n] 的一个排列，我们称它是个好数组。 base[n] = [1, 2, ..., n - 1, n, n] （换句话说，它是一个长度为 n + 1 且包含 1 到 n - 1 恰好各一次，包含 n 两次的一个数组）。比方说， base[1]…

数组哈希表排序

题目描述

给你一个整数数组 nums ，如果它是数组 base[n] 的一个排列，我们称它是个好数组。

base[n] = [1, 2, ..., n - 1, n, n] （换句话说，它是一个长度为 n + 1 且包含 1 到 n - 1 恰好各一次，包含 n 两次的一个数组）。比方说，base[1] = [1, 1] ，base[3] = [1, 2, 3, 3] 。

如果数组是一个好数组，请你返回 true ，否则返回 false 。

注意：数组的排列是这些数字按任意顺序排布后重新得到的数组。

示例 1：

输入：nums = [2, 1, 3]
输出：false
解释：因为数组的最大元素是 3 ，唯一可以构成这个数组的 base[n] 对应的 n = 3 。但是 base[3] 有 4 个元素，但数组 nums 只有 3 个元素，所以无法得到 base[3] = [1, 2, 3, 3] 的排列，所以答案为 false 。

示例 2：

输入：nums = [1, 3, 3, 2]
输出：true
解释：因为数组的最大元素是 3 ，唯一可以构成这个数组的 base[n] 对应的 n = 3 ，可以看出数组是 base[3] = [1, 2, 3, 3] 的一个排列（交换 nums 中第二个和第四个元素）。所以答案为 true 。

示例 3：

输入：nums = [1, 1]
输出：true
解释：因为数组的最大元素是 1 ，唯一可以构成这个数组的 base[n] 对应的 n = 1，可以看出数组是 base[1] = [1, 1] 的一个排列。所以答案为 true 。

示例 4：

输入：nums = [3, 4, 4, 1, 2, 1]
输出：false
解释：因为数组的最大元素是 4 ，唯一可以构成这个数组的 base[n] 对应的 n = 4 。但是 base[n] 有 5 个元素而 nums 有 6 个元素。所以答案为 false 。

提示：

1 <= nums.length <= 100
1 <= num[i] <= 200

lightbulb

解题思路

方法一：计数

我们可以用一个哈希表或数组 $cnt$ 记录数组 $nums$ 中每个元素出现的次数。然后我们判断是否满足以下条件：

$cnt[n] = 2$ ，即数组中最大的元素出现了两次；
对于 $1 \leq i \leq n-1$ ，均满足 $cnt[i] = 1$ ，即数组中除了最大的元素外，其他元素都只出现了一次。

如果满足以上两个条件，那么数组 $nums$ 是一个好数组，否则不是。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $nums$ 的长度。

1

2

3

4

5

6

class Solution:
    def isGood(self, nums: List[int]) -> bool:
        cnt = Counter(nums)
        n = len(nums) - 1
        return cnt[n] == 2 and all(cnt[i] for i in range(1, n))

speed

复杂度分析

指标	值
时间	complexity is O(N) for scanning and counting, where N is the array length. Space complexity is O(N) due to the hash table storing counts for numbers up to n.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect candidates to find the maximum element first.
question_mark
Look for use of hash table or frequency array to verify counts efficiently.
question_mark
Check if candidate quickly returns false on early mismatches to save time.

warning

常见陷阱

外企场景

error
Failing to check that array length matches n + 1, leading to incorrect true results.
error
Miscounting occurrences of the maximum element, allowing invalid arrays to pass.
error
Not validating that numbers 1 to n-1 appear exactly once, missing duplicates or missing numbers.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Check if array is good when numbers 1 to n-1 can appear multiple times but n appears exactly twice.
arrow_right_alt
Check if array is good under larger constraints, up to length 1000, requiring more efficient hash or bitmap usage.
arrow_right_alt
Check if array is good when numbers may be negative, requiring adjusted counting or hash lookup.

help

常见问题

外企场景

继续练习

#2780 合法分割的最小下标 #2766 重新放置石块 #2813 子序列最大优雅度