Medium

题目描述

给你一个长度为 n 的整数数组 nums（n 为偶数）和一个整数 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。

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

示例 1：

输入: nums = [1,2,4,3], limit = 4
输出: 1
解释: 通过 1 次操作，你可以将数组变为 [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 次操作，你可以将数组变为 [2,2,2,2]。你不能将任何数字改变为 3，因为 3 > limit。

示例 3：

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

约束条件：

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

解题思路

这道题的核心思路是枚举所有可能的目标和，并计算每个目标和需要的最少操作次数。

对于每一对 (nums[i], nums[n-1-i])，假设目标和为 x，我们需要分析达到这个和需要多少次操作：

  1. 0次操作：如果 nums[i] + nums[n-1-i] == x，不需要操作
  2. 1次操作：如果通过改变一个数字就能达到目标和，需要1次操作
  3. 2次操作：如果需要改变两个数字才能达到目标和，需要2次操作

关键观察：

  • 对于一对数 (a, b)，假设 a <= b
  • 0次操作：目标和 = a + b
  • 1次操作：目标和在 [1+b, a+limit] 或 [a+1, limit+b] 范围内
  • 2次操作：目标和在 [2, 2*limit] 范围内的其他值

我们使用差分数组技术来高效计算每个目标和对应的总操作次数。对于每一对，我们在对应的区间内增加相应的操作次数。

算法步骤：

  1. 创建差分数组，大小为 2*limit + 2
  2. 对每一对数字，计算在不同目标和下需要的操作次数
  3. 使用差分数组记录区间增量
  4. 通过前缀和还原实际数组
  5. 找到最小值

这种方法的优势是能够在 O(n + limit) 的时间内计算所有可能目标和的操作次数。

代码实现

class Solution {
public:
    int minMoves(vector<int>& nums, int limit) {
        int n = nums.size();
        vector<int> diff(2 * limit + 2, 0);
        
        for (int i = 0; i < n / 2; i++) {
            int a = nums[i], b = nums[n - 1 - i];
            if (a > b) swap(a, b);
            
            // 2 operations for all sums
            diff[2] += 2;
            diff[2 * limit + 1] -= 2;
            
            // 1 operation for some ranges
            diff[1 + a] -= 1;
            diff[limit + b + 1] += 1;
            
            // 0 operations for current sum
            diff[a + b] -= 1;
            diff[a + b + 1] += 1;
        }
        
        int current = 0, result = n;
        for (int i = 2; i <= 2 * limit; i++) {
            current += diff[i];
            result = min(result, current);
        }
        
        return result;
    }
};

class Solution:
    def minMoves(self, nums: List[int], limit: int) -> int:
        n = len(nums)
        diff = [0] * (2 * limit + 2)
        
        for i in range(n // 2):
            a, b = nums[i], nums[n - 1 - i]
            if a > b:
                a, b = b, a
            
            # 2 operations for all sums
            diff[2] += 2
            diff[2 * limit + 1] -= 2
            
            # 1 operation for some ranges
            diff[1 + a] -= 1
            diff[limit + b + 1] += 1
            
            # 0 operations for current sum
            diff[a + b] -= 1
            diff[a + b + 1] += 1
        
        current = 0
        result = n
        for i in range(2, 2 * limit + 1):
            current += diff[i]
            result = min(result, current)
        
        return result

public class Solution {
    public int MinMoves(int[] nums, int limit) {
        int n = nums.Length;
        int[] diff = new int[2 * limit + 2];
        
        for (int i = 0; i < n / 2; i++) {
            int a = nums[i], b = nums[n - 1 - i];
            if (a > b) {
                int temp = a;
                a = b;
                b = temp;
            }
            
            // 2 operations for all sums
            diff[2] += 2;
            diff[2 * limit + 1] -= 2;
            
            // 1 operation for some ranges
            diff[1 + a] -= 1;
            diff[limit + b + 1] += 1;
            
            // 0 operations for current sum
            diff[a + b] -= 1;
            diff[a + b + 1] += 1;
        }
        
        int current = 0, result = n;
        for (int i = 2; i <= 2 * limit; i++) {
            current += diff[i];
            result = Math.Min(result, current);
        }
        
        return result;
    }
}

var minMoves = function(nums, limit) {
    const n = nums.length;
    const diff = new Array(2 * limit + 2).fill(0);
    
    for (let i = 0; i < n / 2; i++) {
        let a = nums[i], b = nums[n - 1 - i];
        if (a > b) [a, b] = [b, a];
        
        // 2 operations for all sums
        diff[2] += 2;
        diff[2 * limit + 1] -= 2;
        
        // 1 operation for some ranges
        diff[1 + a] -= 1;
        diff[limit + b + 1] += 1;
        
        // 0 operations for current sum
        diff[a + b] -= 1;
        diff[a + b + 1] += 1;
    }
    
    let current = 0, result = n;
    for (let i = 2; i <= 2 * limit; i++) {
        current += diff[i];
        result = Math.min(result, current);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n + limit)
空间复杂度O(limit)

其中 n 是数组长度，limit 是给定的上界。我们需要遍历 n/2 对数字，每对数字的处理时间是 O(1)，然后需要遍历所有可能的目标和（最多 2*limit 个），所以总时间复杂度是 O(n + limit)。空间复杂度主要用于存储差分数组。

相关题目