【算法天天练】两数相加等于目标值+有序数组问题

59 阅读 0 评论 39 点赞

我是靠谱客的博主天真歌曲，最近开发中收集的这篇文章主要介绍【算法天天练】两数相加等于目标值+有序数组问题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

在这里插入图片描述
个人思路：
A+B = target
设numbers[0]为A，for循环numbers[1]及后面的数据，枚举是否符合A+B=target 的B值，若无，则设numbers[1]为A，for循环numbers[2]及后面的数据，枚举是否有符合A+B = target的B值，以此类推。

这样的方法显然是很暴力的，倘若题目所给的数组的数据很庞大，那么此解题思路根本不实用。
时间复杂度为O(n2)

优化解题思路

抓关键字 “升序排列的数组” ==>有可能会涉及到二分法/折半查找/双指针

先分成三种情况：
（1）倘若 numbers[i]+numbers[j] === target ，那么直接return i 和 j 即可，但由于题目说下标应从1开始，而非0开始，所以需返回 i+1 和 j+1
（2）倘若 numbers[i]+numbers[j] > target ，那么 numbers[i]+numbers[j+1] > target，此时在升序数组里， j 需向前移动一位
（3）倘若 numbers[i]+numbers[j] < target ，那么 numbers[i-1]+numbers[j] < target，此时在升序数组里， i 需向后移动一位

代码如下：

var twoSum = function(numbers, target) {
let left = 0,right = numbers.length-1;
while(left<=right){
if(numbers[left]+numbers[right] === target){
return [left+1,right+1]
}else if(numbers[left]+numbers[right] < target){
left++
}else{
right--
}
}
};