找到和为指定数值的两个数

题目-找到两个数

一个升序数组,找到两个数和等于特定数的位置。注意索引从1开始并且数组中的一个元素只能用一次。

示例

比如 [1,2,3,4,4,9,56,90], target=8 返回[4,5]

分析

最简单的方法就是循环挨个比较,这样最坏的情况就是循环两次,时间复杂度:o(n * n) = o(n^2)

这样明显不行,看清题目是升序数组,所以其实一次循环就可以。可以从数组前面取一个值,后面取一个值,如果大了,就把后面打的数值前移,如果小了,就把前面的小数值后移。这个最差的情况也是一次循环搞定。所以时间复杂度是:o(n)

 

Just Try

请你自动动手试一下:在线编程环境

想想有没有其他思路?

想想时间和空间复杂度,能否优化一下

真的做不到么?

let you think, think makes you happy!

 

参考答案

左右夹攻的实现如下:

function algorithm(param){
  let target = param[0];
  let arr = param[1];
  let a = 0, b = arr.length - 1;
  for(let i=0; i<arr.length; i++){
    if(arr[a] + arr[b] > target){
      b--;
    }
    if(arr[a] + arr[b] < target){
      a++;
    }
    if(arr[a] + arr[b] == target){
      return [a, b]
    }
  }
}
function main(...param) {
  console.show("参数:" + JSON.stringify(param), "结果:" + algorithm(param))
  testPerformance(algorithm, param)
}
main(10, [1,2,3,4,4,9,56,90]);

请你自动动手试一下:在线编程环境

知识共享署名4.0国际许可协议,转载请保留出处; 部分内容来自网络,若有侵权请联系我:前端学堂 » 找到和为指定数值的两个数

赞 (3) 打赏

评论 2

  1. 前端学堂学习了Reply
  2. chale不错哦Reply

如果对您有帮助,别忘了打赏一下宝宝哦!

支付宝扫一扫打赏

微信扫一扫打赏