我要招人

去企业版

首页 > 试题广场 >

在一长度为 N 的有序数列中寻找两个数，使得两数之和等于某指

[单选题]

在一长度为 N 的有序数列中寻找两个数，使得两数之和等于某指定值的最快的算法的平均时间复杂度是（）

```
O(N)
```
```
O(N^2)
```
```
O(N * log(N))
```
```
O(log(n))
```

查看答案及解析

lazerliu

//双指针法

//*p,*q分别从0和最后一位开始，

//1.如果*p+*q<S,p++;

//2.如果大于，--q;

//3 如果p=q了还没找到就是不存在。

//p和q就遍历了一遍数组，所以是O(n)

发表于 2019-07-28 22:27:26 回复(0)

黄宗文

双指针，两头夹

发表于 2019-09-16 12:05:24 回复(1)

刘-琛

注意是有序数列

发表于 2022-04-22 16:06:45 回复(0)

你的offer对我打了烊

int getSumNum(int[] arr,int Sum)，   //arr为数组，Sum为和 
{
	int i,j;
	for(i = 0, j = n-1; i < j ; )
	{
		if(arr[i] + arr[j] == Sum)
			return ( i , j );
		else if(arr[i] + arr[j] < Sum)
			i++;
		else
			j--;
	}
	return ( -1 , -1 );
}

发表于 2020-04-02 14:16:03 回复(0)

CodingOneLife

target = set()
for i in data:
    if i in target:
        print(i,sum-i)
    else:
        target.add(sum-i)
print("not find")

发表于 2019-07-24 00:06:13 回复(0)

起了一个响亮名字的牛百万

在一个长度为 N 的有序数列中寻找两个数，使得两数之和等于某指定值的最快的算法的平均时间复杂度是 O(logN)。以下是一种解决方案：定义两个指针，一个指向数列的开头，另一个指向数列的末尾。计算两个指针指向的数的和。如果和等于指定值，那么就找到了两个数，结束搜索。如果和小于指定值，将第一个指针向后移动一位，以增加和的值。如果和大于指定值，将第二个指针向前移动一位，以减少和的值。重复步骤2-5，直到找到两个数或者指针相遇。如果指针相遇仍然没有找到两个数，那么说明数列中不存在满足条件的数。这种算法利用了有序数列的特性，在每一步都通过比较当前和与指定值的大小来决定移动哪个指针，从而快速缩小搜索范围。平均时间复杂度为O(logN)。

发表于 2023-10-19 18:09:26 回复(0)

大大大🍍

有序数列俩次二分查找效率 O(2*log(N))==O(log(n))

发表于 2022-08-01 08:36:17 回复(1)

阳光小青年

实际上无序也是O（n），利用一个hash table就好了

发表于 2020-03-29 19:04:38 回复(2)

虔诚的🐷

如果是查找两个数，而不是index，修改数组排序O(NlogN)，随后首尾指针查找O(N)，所以是O(N);

也可用哈希方式存储遍历过的元素，在后续元素遍历时，在哈希表表中查找target-arr[index]的树是否存在即可，也是O(N).

发表于 2019-12-11 19:17:49 回复(0)

LiuWei_Find

left =0

right=length- 1

If left-value + right-value > target:

Right = left + (right-left)/2

Set(Right-Value)

Else if left-value + right-value == target:

Return

else:

Left = left + (right-left)/2

Set(Left-value)

发表于 2019-09-25 07:57:13 回复(0)

提交观点

问题信息

算法工程师复杂度旷视 2019

上传者：小小

难度：

10条回答 202收藏 5044浏览

在一长度为 N 的有序数列中寻找两个数，使得两数之和等于某指

问题信息

热门推荐

相关试题