What pattern should I focus on for Destroy Sequential Targets?

The core pattern is array scanning combined with hash lookup or modulo operations to track which seed destroys the most targets.

How do I handle large arrays in this problem?

Using a hashmap or modulo approach ensures you don't need to compare every element to every other element, making the solution more scalable.

Why is modulo important in this problem?

Modulo helps group numbers that can be destroyed by the same seed, allowing you to track destruction sequences more efficiently.

What is the expected time complexity of this problem?

The time complexity depends on the approach you use, but it can be reduced to O(n) using a hashmap or modulo tracking.

What should I do if multiple numbers destroy the same number of targets?

Return the smallest number among them, as specified in the problem statement.

#2453

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

摧毁一系列目标

给你一个下标从 0 开始的数组 nums ，它包含若干正整数，表示数轴上你需要摧毁的目标所在的位置。同时给你一个整数 space 。你有一台机器可以摧毁目标。给机器输入 nums[i] ，这台机器会摧毁所有位置在 nums[i] + c * space 的目标，其中 c 是任意非负整数。你想摧毁…

数组哈希表计数

题目描述

给你一个下标从 0 开始的数组 nums ，它包含若干正整数，表示数轴上你需要摧毁的目标所在的位置。同时给你一个整数 space 。

你有一台机器可以摧毁目标。给机器输入 nums[i] ，这台机器会摧毁所有位置在 nums[i] + c * space 的目标，其中 c 是任意非负整数。你想摧毁 nums 中 尽可能多 的目标。

请你返回在摧毁数目最多的前提下，nums[i] 的 最小值 。

示例 1：

输入：nums = [3,7,8,1,1,5], space = 2
输出：1
解释：如果我们输入 nums[3] ，我们可以摧毁位于 1,3,5,7,9,... 这些位置的目标。
这种情况下， 我们总共可以摧毁 5 个目标（除了 nums[2]）。
没有办法摧毁多于 5 个目标，所以我们返回 nums[3] 。

示例 2：

输入：nums = [1,3,5,2,4,6], space = 2
输出：1
解释：输入 nums[0] 或者 nums[3] 都会摧毁 3 个目标。
没有办法摧毁多于 3 个目标。
由于 nums[0] 是最小的可以摧毁 3 个目标的整数，所以我们返回 1 。

示例 3：

输入：nums = [6,2,5], space = 100
输出：2
解释：无论我们输入哪个数字，都只能摧毁 1 个目标。输入的最小整数是 nums[1] 。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹
1 <= space <= 10⁹

lightbulb

解题思路

方法一：取模 + 枚举

我们遍历数组 $nums$ ，用哈希表 $cnt$ 统计每个数模 $space$ 后的余数出现的次数。次数越多，意味着可以摧毁的目标越多。我们找到最多次数的组，取组中的最小值即可。

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

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def destroyTargets(self, nums: List[int], space: int) -> int:
        cnt = Counter(v % space for v in nums)
        ans = mx = 0
        for v in nums:
            t = cnt[v % space]
            if t > mx or (t == mx and v < ans):
                ans = v
                mx = t
        return ans

speed

复杂度分析

指标	值
时间	complexity depends on the approach, but using a hashmap or modulo tracking reduces the need for brute-force comparisons, making it much more efficient than checking all possible pairs. Space complexity is also impacted by the need to store counts for each number and its modulo class, which may require O(n) space in the worst case.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Looks for knowledge of hashmaps and modulo operations.
question_mark
Tests the ability to implement efficient algorithms without brute force.
question_mark
Assesses problem-solving skills in optimizing performance with large input sizes.

warning

常见陷阱

外企场景

error
Confusing the seed with the number of destroyed targets, leading to incorrect output.
error
Failing to track numbers modulo space, resulting in inefficient solutions.
error
Not handling large input sizes efficiently, causing timeouts.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if targets are ordered? Does it change the approach?
arrow_right_alt
What happens if all numbers are the same?
arrow_right_alt
Can you optimize further by using binary search on sorted nums?

help

常见问题

外企场景

继续练习

#2442 反转之后不同整数的数目 #2499 让数组不相等的最小总代价 #2404 出现最频繁的偶数元素