Medium

题目描述

给你两个整数数组 nums1 和 nums2。

从 nums1 中移除两个元素，并且所有其他元素都增加（如果是负数则减少）一个整数 x。

结果 nums1 变得等于 nums2。当两个数组包含相同的整数且频率相同时，认为它们相等。

返回能够实现这种等价性的最小可能整数 x。

示例 1：

输入：nums1 = [4,20,16,12,8], nums2 = [14,18,10]
输出：-2
解释：移除索引 [0,4] 处的元素并加上 -2 后，nums1 变为 [18,14,10]。

示例 2：

输入：nums1 = [3,5,5,3], nums2 = [7,7]
输出：2
解释：移除索引 [0,3] 处的元素并加上 2 后，nums1 变为 [7,7]。

提示：

  • 3 <= nums1.length <= 200
  • nums2.length == nums1.length - 2
  • 0 <= nums1[i], nums2[i] <= 1000
  • 测试用例保证存在整数 x，使得 nums1 能够通过移除两个元素并给每个元素加上 x 来变得等于 nums2。

解题思路

解题思路

这道题要求我们从 nums1 中移除两个元素，然后给剩余的每个元素加上一个数 x，使得结果等于 nums2。

核心观察：如果我们已经确定了要移除的两个元素，那么 x 的值就可以通过任意一对对应元素计算得出。为了得到最小的 x，我们需要尝试所有可能的移除方案。

算法步骤：

  1. 排序：对两个数组排序，这样便于后续匹配
  2. 枚举移除方案：枚举所有可能移除两个元素的方案（共 C(n,2) 种）
  3. 验证方案：对每种移除方案：
    • 计算 x = nums2[0] - remaining_nums1[0]
    • 检查剩余元素加上 x 后是否与 nums2 完全匹配
  4. 返回最小值：在所有有效方案中返回最小的 x

优化思路：

  • 由于要找最小的 x，可以优先尝试移除较大的元素
  • 排序后可以更高效地验证两个数组是否匹配

时间复杂度主要由枚举所有移除方案决定，为 O(n²)，其中 n 是 nums1 的长度。

代码实现

class Solution {
public:
    int minimumAddedInteger(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        
        int n = nums1.size();
        int minX = INT_MAX;
        
        // 枚举所有可能移除两个元素的方案
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                vector<int> remaining;
                for (int k = 0; k < n; k++) {
                    if (k != i && k != j) {
                        remaining.push_back(nums1[k]);
                    }
                }
                
                // 计算x值
                int x = nums2[0] - remaining[0];
                
                // 验证是否匹配
                bool valid = true;
                for (int k = 0; k < remaining.size(); k++) {
                    if (remaining[k] + x != nums2[k]) {
                        valid = false;
                        break;
                    }
                }
                
                if (valid) {
                    minX = min(minX, x);
                }
            }
        }
        
        return minX;
    }
};

class Solution:
    def minimumAddedInteger(self, nums1: List[int], nums2: List[int]) -> int:
        nums1.sort()
        nums2.sort()
        
        n = len(nums1)
        min_x = float('inf')
        
        # 枚举所有可能移除两个元素的方案
        for i in range(n):
            for j in range(i + 1, n):
                remaining = []
                for k in range(n):
                    if k != i and k != j:
                        remaining.append(nums1[k])
                
                # 计算x值
                x = nums2[0] - remaining[0]
                
                # 验证是否匹配
                valid = True
                for k in range(len(remaining)):
                    if remaining[k] + x != nums2[k]:
                        valid = False
                        break
                
                if valid:
                    min_x = min(min_x, x)
        
        return min_x

public class Solution {
    public int MinimumAddedInteger(int[] nums1, int[] nums2) {
        Array.Sort(nums1);
        Array.Sort(nums2);
        
        int n = nums1.Length;
        int minX = int.MaxValue;
        
        // 枚举所有可能移除两个元素的方案
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                List<int> remaining = new List<int>();
                for (int k = 0; k < n; k++) {
                    if (k != i && k != j) {
                        remaining.Add(nums1[k]);
                    }
                }
                
                // 计算x值
                int x = nums2[0] - remaining[0];
                
                // 验证是否匹配
                bool valid = true;
                for (int k = 0; k < remaining.Count; k++) {
                    if (remaining[k] + x != nums2[k]) {
                        valid = false;
                        break;
                    }
                }
                
                if (valid) {
                    minX = Math.Min(minX, x);
                }
            }
        }
        
        return minX;
    }
}

var minimumAddedInteger = function(nums1, nums2) {
    nums1.sort((a, b) => a - b);
    nums2.sort((a, b) => a - b);
    
    const n = nums1.length;
    let minX = Infinity;
    
    // 枚举所有可能移除两个元素的方案
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            const remaining = [];
            for (let k = 0; k < n; k++) {
                if (k !== i && k !== j) {
                    remaining.push(nums1[k]);
                }
            }
            
            // 计算x值
            const x = nums2[0] - remaining[0];
            
            // 验证是否匹配
            let valid = true;
            for (let k = 0; k < remaining.length; k++) {
                if (remaining[k] + x !== nums2[k]) {
                    valid = false;
                    break;
                }
            }
            
            if (valid) {
                minX = Math.min(minX, x);
            }
        }
    }
    
    return minX;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n³)需要枚举 O(n²) 种移除方案，每次验证需要 O(n) 时间
空间复杂度O(n)需要额外数组存储移除元素后的剩余数组