题目描述
LeetCode 2540 — 最小公共值 (Easy)
给你两个非递减排序的整数数组 nums1 和 nums2，请你找出两个数组中最小的公共整数。如果不存在公共整数，返回 -1。
一个整数如果在两个数组中至少出现一次，则称为公共整数。
示例 1：
- 输入：
nums1 = [1,2,3], nums2 = [2,4] - 输出：
2 - 解释：两个数组的公共元素为 2，它是最小的。
示例 2：
- 输入：
nums1 = [1,2,3,6], nums2 = [2,3,4,5] - 输出：
2 - 解释：公共元素有 2 和 3，其中最小的是 2。
约束：
1 <= nums1.length, nums2.length <= 10^51 <= nums1[i], nums2[j] <= 10^9nums1和nums2均为非递减排序
核心思路
有序 → 双指针
题目给定的最关键条件：两个数组都已排序（非递减）。这意味着：
- 从左到右遍历时，元素单调不降
- 如果我们用两个指针分别扫描两个数组，较小的那个指针必然落后，不可能被另一个数组后面的元素追上
这正是双指针技巧最经典的应用场景。
策略
初始化 i = 0, j = 0，同时遍历两个数组：
nums1[i] == nums2[j]：找到公共值。由于从左往右扫，第一个相遇的公共值就是最小的，直接返回。nums1[i] < nums2[j]：nums1的当前值太小，不可能在nums2中找到匹配（nums2[j]及之后都更大），i++。nums1[i] > nums2[j]：同理，nums2的当前值太小，j++。
每次比较淘汰一个元素，任何一个数组走到末尾则结束。
解法：双指针
int getCommon(vector<int>& nums1, vector<int>& nums2) {
int n1 = nums1.size(), n2 = nums2.size();
int i = 0, j = 0;
while (i < n1 && j < n2) {
if (nums1[i] == nums2[j]) {
return nums1[i];
}
else if (nums1[i] < nums2[j]) {
i++;
}
else {
j++;
}
}
return -1;
}
复杂度： 时间 O(m + n)，空间 O(1)。每轮循环至少有一个指针前进，最多 m + n 次比较。