2570. 合并两个二维数组 - 求和法

🟢   🔖  数组 哈希表 双指针  🔗 力扣 LeetCode

题目

You are given two 2D integer arrays nums1 and nums2.

• nums1[i] = [idi, vali] indicate that the number with the id idi has a value equal to vali.
• nums2[i] = [idi, vali] indicate that the number with the id idi has a value equal to vali.

Each array contains unique ids and is sorted in ascending order by id.

Merge the two arrays into one array that is sorted in ascending order by id, respecting the following conditions:

• Only ids that appear in at least one of the two arrays should be included in the resulting array.
• Each id should be included only once and its value should be the sum of the values of this id in the two arrays. If the id does not exist in one of the two arrays then its value in that array is considered to be 0.

Return the resulting array. The returned array must be sorted in ascending order by id.

Example 1:

Input: nums1 = [[1,2],[2,3],[4,5]], nums2 = [[1,4],[3,2],[4,1]]

Output: [[1,6],[2,3],[3,2],[4,6]]

Explanation: The resulting array contains the following:

• id = 1, the value of this id is 2 + 4 = 6.
• id = 2, the value of this id is 3.
• id = 3, the value of this id is 2.
• id = 4, the value of this id is 5 + 1 = 6.

Example 2:

Input: nums1 = [[2,4],[3,6],[5,5]], nums2 = [[1,3],[4,3]]

Output: [[1,3],[2,4],[3,6],[4,3],[5,5]]

Explanation: There are no common ids, so we just include each id with its value in the resulting list.

Constraints:

• 1 <= nums1.length, nums2.length <= 200
• nums1[i].length == nums2[j].length == 2
• 1 <= idi, vali <= 1000
• Both arrays contain unique ids.
• Both arrays are in strictly ascending order by id.

题目大意

给你两个 二维 整数数组 nums1 和 nums2.

• nums1[i] = [idi, vali] 表示编号为 idi 的数字对应的值等于 vali 。
• nums2[i] = [idi, vali] 表示编号为 idi 的数字对应的值等于 vali 。

每个数组都包含 互不相同 的 id ，并按 id 以 递增 顺序排列。

请你将两个数组合并为一个按 id 以递增顺序排列的数组，并符合下述条件：

• 只有在两个数组中至少出现过一次的 id 才能包含在结果数组内。
• 每个 id 在结果数组中 只能出现一次 ，并且其对应的值等于两个数组中该 id 所对应的值求和。如果某个数组中不存在该 id ，则认为其对应的值等于 0 。

返回结果数组。返回的数组需要按 id 以递增顺序排列。

示例 1：

输入： nums1 = [[1,2],[2,3],[4,5]], nums2 = [[1,4],[3,2],[4,1]]

输出：[[1,6],[2,3],[3,2],[4,6]]

解释： 结果数组中包含以下元素：

• id = 1 ，对应的值等于 2 + 4 = 6 。
• id = 2 ，对应的值等于 3 。
• id = 3 ，对应的值等于 2 。
• id = 4 ，对应的值等于 5 + 1 = 6 。

示例 2：

输入： nums1 = [[2,4],[3,6],[5,5]], nums2 = [[1,3],[4,3]]

输出：[[1,3],[2,4],[3,6],[4,3],[5,5]]

解释： 不存在共同 id ，在结果数组中只需要包含每个 id 和其对应的值。

提示：

• 1 <= nums1.length, nums2.length <= 200
• nums1[i].length == nums2[j].length == 2
• 1 <= idi, vali <= 1000
• 数组中的 id 互不相同
• 数据均按 id 以严格递增顺序排列

解题思路

使用 双指针 方法高效合并两个有序数组：

1. 定义两个指针 i 和 j，分别指向 nums1 和 nums2 的起始位置。
2. 逐步比较 nums1[i] 和 nums2[j]：
   • 如果 id1 == id2，合并数值 val1 + val2，然后 i++ 和 j++。
   • 如果 id1 < id2，说明 nums1[i] 只存在于 nums1，直接加入 result，然后 i++。
   • 如果 id1 > id2，说明 nums2[j] 只存在于 nums2，直接加入 result，然后 j++。
3. 当一个数组遍历结束后，将另一个数组剩余的部分加入 result。
4. 返回合并后的 result 数组。

复杂度分析

• 时间复杂度：O(n + m)，其中 n 是 nums1.length，m 是 nums2.length，由于两个数组已排序，双指针 i, j 只向前移动，不会回退，时间复杂度为 O(n + m)。
• 空间复杂度：O(n + m)，额外存储 result 数组。

代码

/**
 * @param {number[][]} nums1
 * @param {number[][]} nums2
 * @return {number[][]}
 */
var mergeArrays = function (nums1, nums2) {
	let result = [];
	let i = 0,
		j = 0;

	while (i < nums1.length && j < nums2.length) {
		const [id1, val1] = nums1[i];
		const [id2, val2] = nums2[j];

		if (id1 === id2) {
			result.push([id1, val1 + val2]);
			i++;
			j++;
		} else if (id1 < id2) {
			result.push([id1, val1]);
			i++;
		} else {
			result.push([id2, val2]);
			j++;
		}
	}

	// 处理 nums1 或 nums2 剩余的元素
	while (i < nums1.length) result.push(nums1[i++]);
	while (j < nums2.length) result.push(nums2[j++]);

	return result;
};

相关题目

题号	标题	题解	标签	难度	力扣
21	合并两个有序链表	[✓]	递归 链表	🟢	🀄️ 🔗
1229	安排会议日程 🔒		数组 双指针 排序	🟠	🀄️ 🔗
2363	合并相似的物品	[✓]	数组 哈希表 有序集合 1+	🟢	🀄️ 🔗