跳转至

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

题目描述

给定两个整数数组 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 <= 105
  • -105 <= nums1[i], nums2[i] <= 105

解法

方法一：哈希表

我们初始化一个变量 \(\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\) 是数组的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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;
}

评论