给一个整数数组，找到两个数使得他们的和等于一个给定的数 target。输出这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是 0 到 n-1。你可以假设数组递增有序，O(N)时间完成

Honoria ·

更新时间:2024-09-20

· 989 次阅读

描述

给一个整数数组，找到两个数使得他们的和等于一个给定的数 target。
你需要输出这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是 0 到 n-1。
你可以假设数组递增有序。
请在O(N)时间内完成。

输入

第一行：N个整数，作为数组的元素，空格分开
第二行：target

输出

两个下标，空格隔开。如有多组满足要求，输出靠前的一组。

样例输入

4
2 7 11 15
9

样例输出

0 1

我们看到这个题首先想到的就是双重循环，如果是用双重循环做的话，这个题就非常简单了，但是题目要求要在O(N)时间内完成
我们先来看如果是双重循环我们该怎么写

O(N^2)

static int[] f(int[] arr,int k) {
		for (int i = 0; i < arr.length-1; i++) {
			for (int j = 1; j < arr.length; j++) {
				if(arr[i]+arr[j]==k) {
					return new int[] {i,j};
				}else {
					continue;
				}
			}
		}
		return new int[] {-1,-1};
	}

结果

这个做可以非常简单的解决两个数，但是时间复杂度在O(N^2)

其实实际上我们可以这样想

要在O(N)时间内完成就要说只能用一个循环
假设k是我们要的结果，在数组中找两个下标

k　－　Arr[i]　＝　result　//是不是我们只需要在数组中找到result这个值就好了

考虑如果有重复例如：8　－　４　＝　4　那么我们要找是另一个4而不是我们减的这个4
总结以上：要在数组排除减去的值，在剩下的值中找我们要的结果

代码实现
//O(N)

	static int[] f1(int[] arr,int k) {
		for (int i = 0; i < arr.length; i++) {
			int c = k - arr[i];
			int index = binarySearch(arr, 0, arr.length-1, c);//在这里我们调用了一个二分查找
			if(index != -1 && index != i) {//找到了，而且不是我们减的那个值
				return new int[] {i,index};
			}
		}
		return new int[] {-1,-1};
	}

我在这里调用的是个二分寻找O(lg2N)，调用顺序O(N)

//二分查找
static int binarySearch(int[] arr,int begin,int end,int k) {
		if (begin>end) return -1;//前后指针交叉就是没找到
		int indexMid = (begin+end)>>1;//偶数减一半，奇数减一半+1
		int Val = arr[indexMid];
		if(Val > k)
			return binarySearch(arr, begin, indexMId-1, k);
		else if(Val < k)
			return binarySearch(arr, indexMid+1, end, k);
		return indexMid;
	}

利用 差的方式 这个题有 排序、查找 的基础就可以很简单的解题

作者：Tin know

输出假设 target 数组

1024 个赞