What does 'array scanning plus hash lookup' mean in this problem?

It refers to scanning each pair of nums[i] and nums[n-1-i] while using a hash or prefix sum array to track move ranges for every possible sum.

Can we solve this problem without a prefix sum array?

Yes, but without prefix sums, counting moves for all target sums becomes less efficient and may lead to timeouts on large arrays or limits.

Why does each pair contribute 0, 1, or 2 moves?

Because a pair's current sum might already match the target (0 moves), need one element replaced (1 move), or require changing both numbers (2 moves) to reach a specific sum.

Is it necessary to consider every possible target sum between 2 and 2*limit?

Yes, because each pair's sum range can influence which total sum yields minimal moves, and ignoring any possible sum could miss the optimal solution.

How do we apply this approach to the example nums = [1,2,4,3], limit = 4?

Analyze pairs (1,3) and (2,4), update prefix sums for move ranges, then find the target sum with minimal cumulative moves, which is 1 in this case.

#1674

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

使数组互补的最少操作次数

给你一个长度为偶数 n 的整数数组 nums 和一个整数 limit 。每一次操作，你可以将 nums 中的任何整数替换为 1 到 limit 之间的另一个整数。如果对于所有下标 i （下标从 0 开始）， nums[i] + nums[n - 1 - i] 都等于同一个数，则数组 nums…

数组哈希表前缀和

题目描述

给你一个长度为偶数 n 的整数数组 nums 和一个整数 limit 。每一次操作，你可以将 nums 中的任何整数替换为 1 到 limit 之间的另一个整数。

如果对于所有下标 i（下标从 0 开始），nums[i] + nums[n - 1 - i] 都等于同一个数，则数组 nums 是 互补的 。例如，数组 [1,2,3,4] 是互补的，因为对于所有下标 i ，nums[i] + nums[n - 1 - i] = 5 。

返回使数组互补的最少操作次数。

示例 1：

输入：nums = [1,2,4,3], limit = 4
输出：1
解释：经过 1 次操作，你可以将数组 nums 变成 [1,2,2,3]（加粗元素是变更的数字）：
nums[0] + nums[3] = 1 + 3 = 4.
nums[1] + nums[2] = 2 + 2 = 4.
nums[2] + nums[1] = 2 + 2 = 4.
nums[3] + nums[0] = 3 + 1 = 4.
对于每个 i ，nums[i] + nums[n-1-i] = 4 ，所以 nums 是互补的。

示例 2：

输入：nums = [1,2,2,1], limit = 2
输出：2
解释：经过 2 次操作，你可以将数组 nums 变成 [2,2,2,2] 。你不能将任何数字变更为 3 ，因为 3 > limit 。

示例 3：

输入：nums = [1,2,1,2], limit = 2
输出：0
解释：nums 已经是互补的。

提示：

n == nums.length
2 <= n <= 10⁵
1 <= nums[i] <= limit <= 10⁵
n 是偶数。

lightbulb

解题思路

方法一：差分数组

假设最终的数组中，数对 $\textit{nums}[i]$ 和 $\textit{nums}[n-i-1]$ 的和为 $s$ 。

我们不妨设 $x$ 为 $\textit{nums}[i]$ 和 $\textit{nums}[n-i-1]$ 的较小值，设 $y$ 为 $\textit{nums}[i]$ 和 $\textit{nums}[n-i-1]$ 的较大值。

对于每一对数，我们有以下几种情况：

如果不需要替换，那么 $x + y = s$ 。
如果替换一次，那么 $x + 1 \le s \le y + \textit{limit}$ 。
如果替换两次，那么 $2 \le s \le x$ 或 $y + \textit{limit} + 1 \le s \le 2 \times \textit{limit}$ 。

即：

在 $[2,..x]$ 范围内，需要替换 $2$ 次。
在 $[x+1,..x+y-1]$ 范围内，需要替换 $1$ 次。
在 $[x+y]$ 时，不需要替换。
在 $[x+y+1,..y + \textit{limit}]$ 范围内，需要替换 $1$ 次。
在 $[y + \textit{limit} + 1,..2 \times \textit{limit}]$ 范围内，需要替换 $2$ 次。

我们枚举每一个数对，利用差分数组，更新每个数对在不同区间范围内的替换次数。

最后，我们求出下标 $2$ 到 $2 \times \textit{limit}$ 的前缀和中的最小值，即为最少的替换次数。

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

相似题目：

3224. 使差值相等的最少数组改动次数

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def minMoves(self, nums: List[int], limit: int) -> int:
        d = [0] * (2 * limit + 2)
        n = len(nums)
        for i in range(n // 2):
            x, y = nums[i], nums[-i - 1]
            if x > y:
                x, y = y, x
            d[2] += 2
            d[x + 1] -= 2
            d[x + 1] += 1
            d[x + y] -= 1
            d[x + y + 1] += 1
            d[y + limit + 1] -= 1
            d[y + limit + 1] += 2
        return min(accumulate(d[2:]))

speed

复杂度分析

指标	值
时间	complexity is O(n + limit) due to scanning each pair and updating the prefix sum array, while space complexity is O(limit) to store the range modifications for sums.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Asks about optimizing without checking every possible sum explicitly.
question_mark
Hints at using prefix sum or cumulative counting for range updates.
question_mark
Wants discussion on handling pairs with 0, 1, or 2 required moves.

warning

常见陷阱

外企场景

error
Assuming every pair always requires exactly one move without checking current sum.
error
Overlooking the range boundaries when updating prefix sums, leading to incorrect totals.
error
Using brute-force nested loops over all sums, causing timeouts on large limits.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Finding minimal moves when array can have odd length and one unmatched element.
arrow_right_alt
Allowing replacements outside 1 to limit, introducing negative or larger sums.
arrow_right_alt
Determining complementary arrays under additional constraints, such as fixed first element.

help

常见问题

外企场景

继续练习

#1658 将 x 减到 0 的最小操作数 #1590 使数组和能被 P 整除 #1546 和为目标值且不重叠的非空子数组的最大数目