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

题目-找到两个数 #

一个升序数组，找到两个数和等于特定数的位置。注意索引从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]);

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