博客

题目

给定两个升序排列的数组A,B，长度分别为n和m。要求输出两个数列中元素相加的和刚好等于x的两个数组元素的下标值。

题目思路

暴力做法

for(int i = 0;i<n;i++){
	for(int j = 0;j<m;j++){
			if(a[i]+b[j]==x)cout<<i<<' '<<j<<endl;
	}
}

这种做法没什么好说的就是全部遍历一遍。单个单个比较，复杂度爆炸O(nm)。

双指针算法

for(int i = 0,j = m-1;i<n;i++){
       while(j >= 0&&a[i]+b[j]>x)j--;
       if(j>=0;a[i]+b[j]==x)cout<<i<<' '<<j;
       
   }

这个做法核心思路就是在第一层循环时将指向b数组的j指向b的末尾值，也就是b数组中的最大值，当a数组的数加上b数组的数大于目标值，j就指向前一个较小的数。一直到最终找到目标值。这个算法的复杂度是O(n+m)；

思路

上面的代表i初始指向位置，下面代表j指向位置。

因为

数组是递增的

所以只要a[i]+b[j]<x，说明i以前的所有a[]+b[j]都要小于x，此时i++。

当a[i]+b[j]>x时，说明此时b的值偏大，因为i以后的任意a[]中值都要大于a[i]，此时j- -。

为什么j不用再从后面开始往前，会不会有情况a[i]后面的数加b[j]过了的值等于x呢？


答案是不会的，因为j –的条件是a[i]+b[j]>x，可能是a[i]大或者是b[j]大，但是只有可能是b[j]大，因为a[i]往后的数更大，所以答案只能在b[j]前面小的数。