列表

详情

3132. 找出与数组相加的整数 II

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

从 nums1 中移除两个元素，并且所有其他元素都与变量 x 所表示的整数相加。如果 x 为负数，则表现为元素值的减少。

执行上述操作后，nums1 和 nums2 相等 。当两个数组中包含相同的整数，并且这些整数出现的频次相同时，两个数组 相等 。

返回能够实现数组相等的 最小 整数 x 。

 

示例 1:

输入：nums1 = [4,20,16,12,8], nums2 = [14,18,10]

输出：-2

解释：

移除 nums1 中下标为 [0,4] 的两个元素，并且每个元素与 -2 相加后，nums1 变为 [18,14,10] ，与 nums2 相等。

示例 2:

输入：nums1 = [3,5,5,3], nums2 = [7,7]

输出：2

解释：

移除 nums1 中下标为 [0,3] 的两个元素，并且每个元素与 2 相加后，nums1 变为 [7,7] ，与 nums2 相等。

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: int minimumAddedInteger(vector<int>& nums1, vector<int>& nums2) { } };

python3 解法, 执行用时: 35 ms, 内存消耗: 16.5 MB, 提交时间: 2024-08-09 09:08:50 

class Solution:
    def minimumAddedInteger(self, nums1: List[int], nums2: List[int]) -> int:
        nums1.sort()
        nums2.sort()
        for i in range(2, 0, -1):
            x = nums2[0] - nums1[i]
            it = iter(nums1[i:])
            # 判断 {nums2[j] - x} 是否为 nums1[i:] 的子序列
            # in 会消耗迭代器
            if all(v - x in it for v in nums2):
                return x
        return nums2[0] - nums1[0]

rust 解法, 执行用时: 3 ms, 内存消耗: 2.1 MB, 提交时间: 2024-08-09 09:08:34 

impl Solution {
    pub fn minimum_added_integer(mut nums1: Vec<i32>, mut nums2: Vec<i32>) -> i32 {
        nums1.sort_unstable();
        nums2.sort_unstable();
        // 枚举保留 nums1[2] 或者 nums1[1] 或者 nums1[0]
        // 倒着枚举是因为 nums1[i] 越大答案越小，第一个满足的就是答案
        for i in (1..3).rev() {
            let x = nums2[0] - nums1[i];
            // 在 {nums1[i] + x} 中找子序列 nums2
            let mut j = 0;
            for &v in &nums1[i..] {
                if nums2[j] == v + x && { j += 1; j == nums2.len() } {
                    // nums2 是 {nums1[i] + x} 的子序列
                    return x;
                }
            }
        }
        // 题目保证答案一定存在
        nums2[0] - nums1[0]
    }
}

javascript 解法, 执行用时: 60 ms, 内存消耗: 51.7 MB, 提交时间: 2024-08-09 09:08:00 

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var minimumAddedInteger = function(nums1, nums2) {
    nums1.sort((a, b) => a - b);
    nums2.sort((a, b) => a - b);
    // 枚举保留 nums1[2] 或者 nums1[1] 或者 nums1[0]
    // 倒着枚举是因为 nums1[i] 越大答案越小，第一个满足的就是答案
    for (let i = 2; i > 0; i--) {
        const x = nums2[0] - nums1[i];
        // 在 {nums1[i] + x} 中找子序列 nums2
        let j = 0;
        for (let k = i; k < nums1.length; k++) {
            if (nums2[j] === nums1[k] + x && ++j === nums2.length) {
                // nums2 是 {nums1[i] + x} 的子序列
                return x;
            }
        }
    }
    // 题目保证答案一定存在
    return nums2[0] - nums1[0];
};

golang 解法, 执行用时: 4 ms, 内存消耗: 2.7 MB, 提交时间: 2024-05-01 10:59:24 

func minimumAddedInteger(nums1, nums2 []int) int {
	slices.Sort(nums1)
	slices.Sort(nums2)
	// 枚举保留 nums1[2] 或者 nums1[1] 或者 nums1[0]
	// 倒着枚举是因为 nums1[i] 越大答案越小，第一个满足的就是答案
	for i := 2; i > 0; i-- {
		diff := nums2[0] - nums1[i]
		// 在 {nums1[i] + diff} 中找子序列 nums2
		j := 0
		for _, v := range nums1[i:] {
			if nums2[j] == v+diff {
				j++
				// nums2 是 {nums1[i] + diff} 的子序列
				if j == len(nums2) {
					return diff
				}
			}
		}
	}
	// 题目保证答案一定存在
	return nums2[0] - nums1[0]
}

java 解法, 执行用时: 2 ms, 内存消耗: 41.6 MB, 提交时间: 2024-05-01 10:59:09 

class Solution {
    public int minimumAddedInteger(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        // 枚举保留 nums1[2] 或者 nums1[1] 或者 nums1[0]
        // 倒着枚举是因为 nums1[i] 越大答案越小，第一个满足的就是答案
        for (int i = 2; i > 0; i--) {
            int diff = nums2[0] - nums1[i];
            // 在 {nums1[i] + diff} 中找子序列 nums2
            int j = 0;
            for (int k = i; k < nums1.length; k++) {
                if (nums2[j] == nums1[k] + diff && ++j == nums2.length) {
                    // nums2 是 {nums1[i] + diff} 的子序列
                    return diff;
                }
            }
        }
        // 题目保证答案一定存在
        return nums2[0] - nums1[0];
    }
}

cpp 解法, 执行用时: 3 ms, 内存消耗: 31.5 MB, 提交时间: 2024-05-01 10:58:55 

class Solution {
public:
    int minimumAddedInteger(vector<int>& nums1, vector<int>& nums2) {
        ranges::sort(nums1);
        ranges::sort(nums2);
        // 枚举保留 nums1[2] 或者 nums1[1] 或者 nums1[0]
        // 倒着枚举是因为 nums1[i] 越大答案越小，第一个满足的就是答案
        for (int i = 2; i; i--) {
            int diff = nums2[0] - nums1[i];
            // 在 {nums1[i] + diff} 中找子序列 nums2
            int j = 0;
            for (int k = i; k < nums1.size(); k++) {
                if (nums2[j] == nums1[k] + diff && ++j == nums2.size()) {
                    // nums2 是 {nums1[i] + diff} 的子序列
                    return diff;
                }
            }
        }
        // 题目保证答案一定存在
        return nums2[0] - nums1[0];
    }
};

python3 解法, 执行用时: 39 ms, 内存消耗: 16.4 MB, 提交时间: 2024-05-01 10:58:41 

class Solution:
    def minimumAddedInteger(self, nums1: List[int], nums2: List[int]) -> int:
        nums1.sort()
        nums2.sort()
        # 枚举保留 nums1[2] 或者 nums1[1] 或者 nums1[0]
        # 倒着枚举是因为 nums1[i] 越大答案越小，第一个满足的就是答案
        for i in range(2, 0, -1):
            diff = nums2[0] - nums1[i]
            # 在 {nums1[i] + diff} 中找子序列 nums2
            j = 0
            for v in nums1[i:]:
                if nums2[j] == v + diff:
                    j += 1
                    # nums2 是 {nums1[i] + diff} 的子序列
                    if j == len(nums2):
                        return diff
        # 题目保证答案一定存在
        return nums2[0] - nums1[0]

上一题

© 2024 leetcode.cn