LeetCode 1674. 使数组互补的最少操作次数

约 5 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 字节
标签
数组 哈希表 前缀和

题目描述

✅ 1674. 使数组互补的最少操作次数

image-20260929110051663

image-20260929110051865

题意分析

数组长度为偶数，每次可以把一个元素改成 [1, limit] 中的任意值。要求所有对称位置 i 与 n - 1 - i 的两数之和相同，求最少修改次数；这个共同目标和可以自由选择。

解法：差分统计修改代价

核心思路

[!blue]

每个元素只属于一个对称数对。因此固定目标和 x 后，各对可以独立选择最少修改方式，总修改数就是各对代价之和。两个合法元素的和只能位于 [2, 2*limit]，枚举这个范围内的目标即可。

对一对数，令较小者为 lo、较大者为 hi。修改两个元素可以达到任意合法目标和，所以先把全范围代价设为二。若只改一个元素，保留 lo 可以得到 [lo+1, lo+limit]，保留 hi 可以得到 [hi+1, hi+limit]。由于 1 <= lo <= hi <= limit，这两个区间一定相接或重叠，合起来恰好是 [lo+1, hi+limit]。

所以目标在上述并集内时，至多修改一次；若目标还恰好等于原和 lo+hi，则完全不用修改。原和一定在一次修改的可达区间内，因此单对代价可以表示成三层叠加：全范围加二，一次修改区间减一，原和这个单点再减一。其他目标既不能保持原值，也不能只改一个，最少正好需要两次。

如果对每一对都遍历全部目标，开销会变成两者相乘。差分数组可以在常数次修改中记录整段贡献：对闭区间 [l, r] 加上 delta，只需在 diff[l] 加 delta、diff[r+1] 减 delta。单点也视为长度为一的区间，所以原和处减一后，要在后一位置恢复。

每对只写入这三组边界事件。所有对处理完后，从目标和二开始累加差分，当前前缀和就是选择该目标时所有数对的总代价；取其中最小值即可得到全局最优答案。

解题步骤

  1. 建立长度为 2*limit + 2 的差分数组，为合法范围右端后一格保留哨兵。
  2. 只遍历前半段下标，每次与对应后半段元素组成一对，取得 lo、hi。
  3. 对 [2, 2*limit] 加二，对 [lo+1, hi+limit] 减一，对原和单点再减一。
  4. 扫描所有合法目标和，用前缀和恢复总代价并维护最小值。

代码实现

class Solution {
    public int minMoves(int[] nums, int limit) {
        int n = nums.length;
        // diff 记录目标和 x 上的代价增量，x 的有效范围是 [2, 2*limit]。
        int[] diff = new int[2 * limit + 2];

        for (int i = 0; i < n / 2; i++) {
            int lo = Math.min(nums[i], nums[n - 1 - i]);
            int hi = Math.max(nums[i], nums[n - 1 - i]);

            // 默认这一对要改两个数。
            diff[2] += 2;
            diff[2 * limit + 1] -= 2;
            // 落在 [lo+1, hi+limit] 内只需改一个数。
            diff[lo + 1] -= 1;
            diff[hi + limit + 1] += 1;
            // 恰好等于原和时一个都不用改。
            diff[lo + hi] -= 1;
            diff[lo + hi + 1] += 1;
        }

        int ans = n;
        int cur = 0;

        for (int x = 2; x <= 2 * limit; x++) {
            cur += diff[x];
            ans = Math.min(ans, cur);
        }

        return ans;
    }
}

func minMoves(nums []int, limit int) int {
    n := len(nums)
    // diff 记录目标和 x 上的代价增量，x 的有效范围是 [2, 2*limit]。
    diff := make([]int, 2*limit+2)

    for i := 0; i < n/2; i++ {
        lo, hi := nums[i], nums[n-1-i]
        if lo > hi {
            lo, hi = hi, lo
        }

        // 默认这一对要改两个数。
        diff[2] += 2
        diff[2*limit+1] -= 2
        // 落在 [lo+1, hi+limit] 内只需改一个数。
        diff[lo+1]--
        diff[hi+limit+1]++
        // 恰好等于原和时一个都不用改。
        diff[lo+hi]--
        diff[lo+hi+1]++
    }

    ans, cur := n, 0
    for x := 2; x <= 2*limit; x++ {
        cur += diff[x]
        if cur < ans {
            ans = cur
        }
    }

    return ans
}

复杂度分析

  • 时间复杂度：$O(n+limit)$。每对写入固定数量的差分事件，随后扫描 2*limit - 1 个目标和。
  • 空间复杂度：$O(limit)$，用于差分数组。

关键点总结

[!green]

  • 固定共同目标后，各个对称数对没有共享元素，最少修改数可以直接相加。
  • 一次修改的区间来自“保留较小值”与“保留较大值”两种选择的并集。
  • 代价用全域、区间和单点三层贡献表示，差分只记录边界变化。

易错点总结

[!yellow]

  • 只考虑修改较大或较小的一项，会漏掉一次修改区间的另一部分。
  • 原和处应追加一次减一，不能直接把差分值赋成零，否则会抹掉其他数对的贡献。
  • 区间右端的恢复事件写在 r + 1，不是 r。
  • 只扫描 [2, 2*limit]，零、一以及右侧哨兵都不是合法目标和。

相似题目

题目 难度 关联与区别
370. 区间加法 中等 每个镜像数对对不同目标和的操作费用形成区间，可用差分叠加所有数对费用。
798. 得分最高的最小轮调 困难 同样把每个对象对答案参数的贡献表示为若干区间，再扫描参数域寻找全局最优。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/81001835
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！