admin管理员组文章数量:1122853
『力扣每日一题13』:给定一个整数sum,从有N个有序元素的数组中寻找元素a,b,使得a+b的结果最接近sum,最接近sum,最快的平均时间复杂度是?
一、题目
给定一个整数 sum ,从有 N 个有序元素的数组中寻找元素 a,b ,使得 a+b 的结果最接近 sum ,最接近 sum ,最快的平均时间复杂度是?
二、思路解析
我们定义两个指针,一个指向数组的头部,一个指向数组的尾部。
然后再通过计算两个指针所指元素之和与给定整数 sum 之间的差值,来判断应该向左移动指针还是向右移动指针『大于 sum 则尾部指针向左移,反之亦然』。
直到找到和sum最接近的两个元素。
而平均时间复杂度为 O(N) ,其中 N 为数组的长度。因为我们只需要遍历整个数组一次,每次移动指针的操作需要 O(1) 的时间复杂度。
以上就是本篇博客的全部内容啦,如有不足之处,还请各位指出,期待能和各位一起进步!
本文标签:
版权声明:本文标题:『力扣每日一题13』:给定一个整数sum,从有N个有序元素的数组中寻找元素a,b,使得a+b的结果最接近sum,最接近sum,最快的平均时间复杂度是? 内容由网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:http://www.betaflare.com/biancheng/1702263222a567669.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论