3682. Minimum Index Sum of Common Elements 🔒

题目描述

You are given two integer arrays nums1 and nums2 of equal length n.

We define a pair of indices (i, j) as a good pair if nums1[i] == nums2[j].

Return the minimum index sum i + j among all possible good pairs. If no such pairs exist, return -1.

Example 1:

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

Output: 1

Explanation:

Common elements between nums1 and nums2 are 1 and 3.
For 3, [i, j] = [0, 1], giving an index sum of i + j = 1.
For 1, [i, j] = [2, 0], giving an index sum of i + j = 2.
The minimum index sum is 1.

Example 2:

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

Output: 2

Explanation:

Common elements between nums1 and nums2 are 1 and 2.
For 1, [i, j] = [1, 1], giving an index sum of i + j = 2.
For 2, [i, j] = [2, 0], giving an index sum of i + j = 2.
The minimum index sum is 2.

Example 3:

Input: nums1 = [6,4], nums2 = [7,8]

Output: -1

Explanation:

Since no common elements between nums1 and nums2, the output is -1.

Constraints:

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\) 是数组的长度。

Python3JavaC++GoTypeScript

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

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;
    }
}

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;
    }
};

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
}

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;
}

3682. Minimum Index Sum of Common Elements 🔒

题目描述

解法

方法一：哈希表

评论