本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。给你两个整数数组nums1和nums2它们已经按非降序排序请你返回两个数组的最小公共整数。如果两个数组nums1和nums2没有公共整数请你返回-1。如果一个整数在两个数组中都至少出现一次那么这个整数是数组nums1和nums2公共的。示例 1输入nums1[1,2,3],nums2[2,4]输出2解释两个数组的最小公共元素是2所以我们返回2。示例 2输入nums1[1,2,3,6],nums2[2,3,4,5]输出2解释两个数组中的公共元素是2和32是较小值所以返回2。提示1 nums1.length, nums2.length 10^51 nums1[i], nums2[j] 10^9nums1和nums2都是非降序的。方法 双指针设n nn是n u m s 1 nums_1nums1​的长度m mm是n u m s 2 nums_2nums2​的长度。找最小公共值首先关注两个数组的最小值也就是比较x n u m s 1 [ 0 ] xnums_1[0]xnums1​[0]和y n u m s 2 [ 0 ] y nums_2[0]ynums2​[0]的大小如果x y xyxy由于两个数组都是递增的所以x xx是最小的公共值如果x y x yxy那么x xx也小于n u m s 2 nums_2nums2​的其余元素所以x xx不可能是公共值排除问题变成n u m s 1 nums_1nums1​的后缀[ 1 , n − 1 ] [1, n-1][1,n−1]和n u m s 2 nums_2nums2​的最小公共值。对于这个子问题做法是一样的比较n u m s 1 [ 1 ] nums_1[1]nums1​[1]和n u m s 2 [ 0 ] nums_2[0]nums2​[0]的大小。如果x y x yxy那么y yy也小于n u m s 1 nums_1nums1​的其余元素所以y yy不可能是公共值排除问题变成n u m s 1 nums_1nums1​和n u m s 2 nums_2nums2​的后缀[ 1 , m − 1 ] [1, m-1][1,m−1]的最小公共值。对于这个子问题做法是一样的比较n u m s 1 [ 0 ] nums_1[0]nums1​[0]和n u m s 2 [ 1 ] nums_2[1]nums2​[1]的大小。用两个下标i ii和j jj表示当前要比较的n u m s 1 [ i ] nums_1[i]nums1​[i]和n u m s 2 [ j ] nums_2[j]nums2​[j]的大小。classSolution{publicintgetCommon(int[]nums1,int[]nums2){inti0,nnums1.length;intj0,mnums2.length;while(injm){if(nums1[i]nums2[j]){returnnums1[i];}if(nums1[i]nums2[j]){i;}else{j;}}return-1;}}classSolution{public:intgetCommon(vectorintnums1,vectorintnums2){inti0,nnums1.size();intj0,mnums2.size();while(injm){if(nums1[i]nums2[j]){returnnums1[i];}if(nums1[i]nums2[j]){i;}else{j;}}return-1;}};classSolution:defgetCommon(self,nums1:List[int],nums2:List[int])-int:i,n0,len(nums1)j,m0,len(nums2)whileinandjm:ifnums1[i]nums2[j]:returnnums1[i]ifnums1[i]nums2[j]:i1else:j1return-1# 写法2classSolution:defgetCommon(self,nums1:List[int],nums2:List[int])-int:returnmin(set(nums1)set(nums2),default-1)funcgetCommon(nums1,nums2[]int)int{i,n:0,len(nums1)j,m:0,len(nums2)forinjm{ifnums1[i]nums2[j]{returnnums1[i]}ifnums1[i]nums2[j]{i}else{j}}return-1}implSolution{pubfnget_common(nums1:Veci32,nums2:Veci32)-i32{letnnums1.len();letmnums2.len();letmuti0;letmutj0;whileinjm{ifnums1[i]nums2[j]{returnnums1[i];}ifnums1[i]nums2[j]{i1;}else{j1;}}-1}}vargetCommonfunction(nums1,nums2){leti0,nnums1.length;letj0,mnums2.length;while(injm){if(nums1[i]nums2[j]){returnnums1[i];}if(nums1[i]nums2[j]){i;}else{j;}}return-1;};intgetCommon(int*nums1,intnums1Size,int*nums2,intnums2Size){inti0,j0;while(inums1Sizejnums2Size){if(nums1[i]nums2[j]){returnnums1[i];}if(nums1[i]nums2[j]){i;}else{j;}}return-1;}复杂度分析时间复杂度O ( n m ) O(nm)O(nm)其中n nn是n u m s 1 nums_1nums1​的长度m mm是n u m s 2 nums_2nums2​的长度。空间复杂度O ( 1 ) O(1)O(1)。相似题目[[Leetcode 350. 两个数组的交集 II]][[LeetCode 88. 合并两个有序数组【数组,双指针】简单]]