企业官网建设流程全解析

LeetCode 每日一题笔记

0. 前言

• 日期：2026.05.13
• 题目：1674. 使数组互补的最少操作次数
• 难度：中等
• 标签：数组、差分数组、贪心、前缀和

1. 题目理解

问题描述：
给你一个长度为偶数n的整数数组nums和一个整数limit。每次操作可以将数组中任意元素替换为1~limit之间的其他整数。
当数组满足nums[i] + nums[n-1-i]对所有i都等于同一个数时，数组称为互补数组。
求使数组变为互补数组所需的最少操作次数。

示例：

输入：nums = [1,2,4,3],limit = 4
输出：1
解释：
修改nums[2]为2，数组变为[1,2,2,3]。
此时1+3=4、2+2=4，所有互补对的和均为4，仅需1次操作。

2. 解题思路

核心观察

• 互补数组的核心是：所有(nums[i], nums[n-1-i])对的和必须相等，设为x。
• 对每一对(a, b)，修改次数与目标和x的关系：
  • x == a + b：无需修改，操作次数0；
  • min(a,b)+1 ≤ x ≤ max(a,b)+limit：修改其中一个数即可，操作次数1；
  • 其他情况：两个数都要修改，操作次数2。
• 利用差分数组快速统计所有可能x对应的总操作次数，再取最小值。

算法步骤

1. 初始化差分数组diff，长度为2*limit+2；
2. 遍历每一对互补元素(a, b)：
   • 初始所有x的操作次数加2；
   • 对cost=1的区间[min(a,b)+1, max(a,b)+limit]，操作次数减1；
   • 对cost=0的点sum=a+b，操作次数再减1；
3. 计算差分数组的前缀和，遍历所有可能的x，找出最小操作次数。

3. 代码实现

classSolution{publicintminMoves(int[]nums,intlimit){int[]diff=newint[2*limit+2];intn=nums.length;for(inti=0;i<n/2;i++){inta=nums[i];intb=nums[n-1-i];intsum=a+b;// 1. 初始：所有x需要2次修改diff[2]+=2;diff[2*limit+1]-=2;// 2. 进入cost=1的区间，修改次数减1intl=Math.min(a,b)+1;intr=Math.max(a,b)+limit;diff[l]-=1;diff[r+1]+=1;// 3. 进入cost=0的点，修改次数再减1diff[sum]-=1;diff[sum+1]+=1;}// 计算前缀和，找出最小修改次数intminOps=Integer.MAX_VALUE;intcurrentOps=0;for(intx=2;x<=2*limit;x++){currentOps+=diff[x];minOps=Math.min(minOps,currentOps);}returnminOps;}}

4. 代码优化说明

• 差分数组仅需一次遍历即可完成区间更新，避免了暴力枚举所有x的O(n*limit)复杂度；
• 区间更新逻辑清晰，将三种修改次数的场景转化为差分数组的加减操作；
• 前缀和计算仅需一次遍历，整体复杂度为线性级。

5. 复杂度分析

• 时间复杂度：O(n+limit)O(n + limit)O(n+limit)

  • 遍历互补对：O(n/2)O(n/2)O(n/2)；
  • 差分数组前缀和遍历：O(2∗limit)O(2*limit)O(2∗limit)；
  • 总时间复杂度为线性级。

• 空间复杂度：O(limit)O(limit)O(limit)

  • 差分数组大小为2*limit+2，与limit成正比。

6. 总结

• 核心思路是差分数组 + 前缀和，将多对元素的修改次数统计转化为区间更新问题；
• 关键技巧：对每一对互补元素，按目标和x划分三种修改次数区间，用差分数组高效统计；
• 本题是差分数组在区间更新问题中的经典应用，通过一次遍历完成所有区间更新，再通过前缀和得到结果。

关键点回顾

1. 互补数组的核心是所有互补对的和相等；
2. 对每一对元素，修改次数分为0/1/2三种情况，对应不同的目标和区间；
3. 差分数组可高效实现区间加减操作，是解决此类问题的核心工具。