3682. 公共元素的最小索引和 🔒

October 6, 2025 · View on GitHub

English Version

题目描述

给定两个整数数组 nums1 和 nums2，长度都为 n。

如果 nums1[i] == nums2[j]，我们定义下标对 (i, j) 是 好数对。

返回所有可能的好数对中 i + j 的最小索引和。如果不存在这样的数对，则返回 -1。

示例 1：

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

输出：1

解释：

nums1 和 nums2 之间的公共元素是 1 和 3。
对于 3，[i, j] = [0, 1]，得到下标和是 i + j = 1。
对于 1，[i, j] = [2, 0]，得到下标和是 i + j = 2。
最小下标和是 1。

示例 2：

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

输出：2

解释：

nums1 和 nums2 之间的公共元素是 1 和 2。
对于 1，[i, j] = [1, 1]，得到下标和是 i + j = 2。
对于 2，[i, j] = [2, 0]，得到下标和是 i + j = 2。
最小下标和是 2。

示例 3：

输入：nums1 = [6,4], nums2 = [7,8]

输出：-1

解释：

由于 nums1 和 nums2 之间没有公共元素，输出为 -1。

提示：

1 <= nums1.length == nums2.length <= 10⁵
-10⁵ <= nums1[i], nums2[i] <= 10⁵

解法

方法一：哈希表

我们初始化一个变量 $\textit{ans}$ 为无穷大，表示当前的最小索引和，用一个哈希表 $\textit{d}$ 来存储数组 $\textit{nums2}$ 中每个元素第一次出现的索引。

然后我们遍历数组 $\textit{nums1}$ ，对于每个元素 $\textit{nums1}[i]$ ，如果它在 $\textit{d}$ 中存在，我们就计算它的索引和 $i + \textit{d}[\textit{nums1}[i]]$ ，并更新 $\textit{ans}$ 。

最后如果 $\textit{ans}$ 仍然是无穷大，说明没有找到任何公共元素，返回 -1；否则返回 $\textit{ans}$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组的长度。

Python3

class Solution:
    def minimumSum(self, nums1: List[int], nums2: List[int]) -> int:
        d = {}
        for i, x in enumerate(nums2):
            if x not in d:
                d[x] = i
        ans = inf
        for i, x in enumerate(nums1):
            if x in d:
                ans = min(ans, i + d[x])
        return -1 if ans == inf else ans

Java

class Solution {
    public int minimumSum(int[] nums1, int[] nums2) {
        int n = nums1.length;
        final int inf = 1 << 30;
        Map<Integer, Integer> d = new HashMap<>();
        for (int i = 0; i < n; i++) {
            d.putIfAbsent(nums2[i], i);
        }
        int ans = inf;
        for (int i = 0; i < n; i++) {
            if (d.containsKey(nums1[i])) {
                ans = Math.min(ans, i + d.get(nums1[i]));
            }
        }
        return ans == inf ? -1 : ans;
    }
}

C++

class Solution {
public:
    int minimumSum(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        const int inf = INT_MAX;
        unordered_map<int, int> d;
        for (int i = 0; i < n; i++) {
            if (!d.contains(nums2[i])) {
                d[nums2[i]] = i;
            }
        }
        int ans = inf;
        for (int i = 0; i < n; i++) {
            if (d.contains(nums1[i])) {
                ans = min(ans, i + d[nums1[i]]);
            }
        }
        return ans == inf ? -1 : ans;
    }
};

Go

func minimumSum(nums1 []int, nums2 []int) int {
	const inf = 1 << 30
	d := make(map[int]int)
	for i, x := range nums2 {
		if _, ok := d[x]; !ok {
			d[x] = i
		}
	}
	ans := inf
	for i, x := range nums1 {
		if j, ok := d[x]; ok {
            ans = min(ans, i + j)
		}
	}
	if ans == inf {
		return -1
	}
	return ans
}

TypeScript

function minimumSum(nums1: number[], nums2: number[]): number {
    const n = nums1.length;
    const inf = 1 << 30;
    const d = new Map<number, number>();
    for (let i = 0; i < n; i++) {
        if (!d.has(nums2[i])) {
            d.set(nums2[i], i);
        }
    }
    let ans = inf;
    for (let i = 0; i < n; i++) {
        if (d.has(nums1[i])) {
            ans = Math.min(ans, i + (d.get(nums1[i]) as number));
        }
    }
    return ans === inf ? -1 : ans;
}