题目:
给定一个已按照升序排列的有序数组,找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2。
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
看到这道题有点小感触,想到最开始刷 leetcode 就是被这道简单的提劝退的
印象深刻,现在还记得,第一看好简单,马上就用 indexOf 写了,然后肯定没通过,泪目
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
var twoSum = function (numbers, target) {
let index1 = 0,
index2 = -1
while (index1 < numbers.length) {
index2 = numbers.indexOf(target - numbers[index1])
if (index2 === -1) {
index1++
} else {
return index1 < index2
? [index1 + 1, index2 + 1]
: [index2 + 1, index1 + 1]
}
}
return index1 < index2
? [index1 + 1, index2 + 1]
: [index2 + 1, index1 + 1]
}
现在看,那时候不仅没注意复杂度的问题,而且逻辑上也有些问题,没有考虑 target 由 numbers 有两个相同是数组成的情况
来看看原来看到的题解吧,之前一直看不明白,为什么要把差值存起,刷了动态规划的题, 再回来看这个就觉得好简单
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
var twoSum = function (numbers, target) {
var a = []
for (var i = 0, len = numbers.length; i < len; i++) {
var tmp = target - numbers[i]
if (a[tmp] !== undefined) return [a[tmp] + 1, i + 1]
a[numbers[i]] = i
}
}
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
var twoSum = function (numbers, target) {
let dp = new map(),
len = numbers.length
for (let i = 0; i < len; i++) {
let tmp = target - numbers[i]
if (dp.has(tmp)) {
return [dp.get(tmp) + 1, i + 1]
}
dp.set(numbers[i], i)
}
}
以上的解法都没有用到升序排列这个条件,其实看到有序最应该想到的就是二分法查找
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
var twoSum = function (numbers, target) {
let len = numbers.length,
left = 0,
right = len - 1,
mid = 0
for (let i = 0; i < len; ++i) {
left = i + 1
while (left <= right) {
mid = parseInt((right - left) / 2) + left
if (numbers[mid] == target - numbers[i]) {
return [i + 1, mid + 1]
} else if (numbers[mid] > target - numbers[i]) {
right = mid - 1
} else {
left = mid + 1
}
}
}
return [-1, -1]
}
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
var twoSum = function (numbers, target) {
let left = 0,
right = numbers.length - 1
while (left < right) {
// 当两个指针对应的元素和等于 target直接返回
if (numbers[left] + numbers[right] === target) {
return [left + 1, right + 1]
} else if (numbers[left] + numbers[right] > target) {
// 当和大于target,则右侧减小(较大的值减小)
right--
} else {
// 当和小于target,则左侧增大(较小的值增大)
left++
}
}
}