LeetCode 每日一题笔记

0. 前言

• 日期：2026.05.19
• 题目：2540. 最小公共值
• 难度：简单
• 标签：数组、双指针、哈希表

1. 题目理解

问题描述： 给定两个按非降序排序的整数数组 nums1 和 nums2，请返回它们的最小公共整数。如果不存在公共整数，则返回 -1。

示例：

输入：nums1 = [1,2,3], nums2 = [2,4] 输出：2 解释：两个数组的最小公共元素是 2。

输入：nums1 = [1,2,3,6], nums2 = [2,3,4,5] 输出：2 解释：两个数组的公共元素是 2 和 3，其中 2 是较小值。

2. 解题思路

核心观察

• 两数组已按非降序排序，可使用双指针高效遍历，类似归并排序的合并过程；
• 利用数组的有序性，只需一次遍历即可找到第一个公共元素，即最小公共值；
• 也可使用哈希表，但会牺牲有序性带来的性能优势，且空间复杂度更高。

算法步骤

1. 初始化双指针 i 和 j，分别指向 nums1 和 nums2 的起始位置；
2. 比较 nums1[i] 和 nums2[j]：
   • 若相等，直接返回该值（有序数组中第一个相等值即为最小值）；
   • 若 nums1[i] > nums2[j]，移动 j 指针；
   • 若 nums1[i] < nums2[j]，移动 i 指针；
3. 遍历结束未找到公共值，返回 -1。

3. 代码实现

package lc2540;

import java.util.HashSet;

public class Solution {
    public int getCommon(int[] nums1, int[] nums2) {
        HashSet<Integer> set = new HashSet<>();

        if (nums1.length > nums2.length) {
            for (int num : nums2) {
                set.add(num);
            }
            for (int num : nums1) {
                if (set.contains(num)) {
                    return num;
                }
            }
        } else {
            for (int num : nums1) {
                set.add(num);
            }
            for (int num : nums1) {
                if (set.contains(num)) {
                    return num;
                }
            }
        }

        return -1;
    }
}

4. 代码优化说明

减少了分支判断，直接利用双指针遍历有序数组，避免了哈希表的额外空间开销，代码更简洁高效：

package lc2540;

public class Solution {
    public int getCommon(int[] nums1, int[] nums2) {
        int i = 0, j = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] == nums2[j]) {
                return nums1[i];
            }
            if (nums1[i] < nums2[j]) {
                i++;
            } else {
                j++;
            }
        }
        return -1;
    }
}

5. 复杂度分析

• 时间复杂度：$O(n+m)$ 双指针遍历两个数组，每个元素最多被访问一次。
• 空间复杂度：$O(1)$ 仅使用常数级额外空间，无哈希表等数据结构开销。

6. 总结

• 核心思路是双指针遍历有序数组，利用数组的非降序特性直接找到第一个公共元素；
• 优化后的双指针解法时间和空间复杂度均优于哈希表解法，是本题最优方案；
• 关键技巧：有序数组的双指针遍历是解决此类问题的经典方法，避免了额外的空间开销和分支判断。