首页 > 试题广场 >

给定一个按升序排列的整数数组 以及一个正整数 ，...

[不定项选择题]

给定一个按升序排列的整数数组   以及一个正整数  ，现在需要在数组   中查找两个元素   和  ，使得  ，请问最优算法的时间复杂度是多少？

查看正确选项
添加回答
南乔可休头像 南乔可休
因为是按照升序排列的有序数组，所以可以使用双指针，其中一个指针指向arr[0]，另一个指针指向arr[n-1]，结果最多只需要将数组遍历一次即可，所以时间复杂度为O(n)。
发表于 2019-03-24 10:14:37 回复(0)
牛客9858138号头像 牛客9858138号
有bug?，图片不显示，显示img标签
发表于 2018-12-21 08:37:07 回复(0)
一颗玉米子头像 一颗玉米子
两遍哈希表，我们把包含有 n 个元素的列表遍历两次。由于哈希表将查找时间缩短到 O(1) ，所以时间复杂度为 O(n)。
发表于 2020-09-11 09:28:49 回复(0)
提交观点

问题信息

前端工程师 2019 有赞
上传者：小小
难度：
3条回答 1974浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号