题目描述
给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2。
说明:
1 2
| 返回的下标值(index1 和 index2)不是从零开始的。 你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素。
|
示例:
1 2 3
| 输入: numbers = [2, 7, 11, 15], target = 9 输出: [1,2] 解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
|
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
标签 数组 双指针 二分查找
解法一:双循环,暴力
时间复杂度:O(n^2)
这个很简单,遍历每个元素x,并查找是否存在一个值与target - x 相等的目标元素。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
|
var twoSum = function(numbers, target) { let res = [] for ( let i = 0; i < numbers.length; i++ ) { for ( let j = i+1; j < numbers.length; j++ ) { if ( numbers[ i ] + numbers[ j ] === target ) { i++, j++ res = [i,j] return res } } } };
|
解法二:hash表
时间复杂度:O(n)
1 2 3
| x + y = target y = target - x x + (target - x) = target
|
套入题目的例子,遍历数组,数组遍历的当前值为numbers[i],那么 y 应该是 target - numbers[i]。
所以,只要在遍历的时候确定target - numbers[i]在数组里有,返回对应下标。
hash表方法有两次哈希表方法和一次哈希表方法。
两次hash表方法,在第一次迭代中,我们将每个元素的值和它的索引添加到表中。然后,在第二次迭代中,我们将检查每个元素所对应的目标元素(target−numbers[i])是否存在于表中。
一次hash表方法,下面代码所示。
1 2 3 4 5 6 7 8 9 10 11 12
| var twoSum = function(numbers, target) { let map = new Map() for(let i = 0; i < numbers.length; i ++) {
if(map.has(target - numbers[i])) { return [map.get(target - numbers[i]) + 1, i + 1] } map.set(numbers[i], i) } };
|
解法三:双向指针
由于数组是有序的,只需要双指针即可。一个left指针,一个right指针, 如果 left + right 值大于 target 则 right左移动, 否则 left 右移。
如果数组无序,需要先排序。
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| var twoSum = function(numbers, target) { let left = 0; let right = numbers.length while(left < right) { if(numbers[left] + numbers[right] === target) { return [left + 1, right + 1] } else if(numbers[left] + numbers[right] < target) { left ++ } else { right -- } } };
|
解法四:二分查找
时间复杂度:O(n log n)
- x + y = target, y = target - x
- 遍历 numbers , 利用二分查找找 target - numbers[i]
- 注意题目要求,其中 index1 必须小于 index2,而且你不可以重复使用相同的元素。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
|
const NOT_FOUND = -1 var twoSum = function(numbers, target) { for (let i = 0; i < numbers.length; i++) { let y = target - numbers[i] let res = binarySearch(numbers, y) if(res !== NOT_FOUND && i !== res){ return i < res ? [i + 1, res + 1] : [res + 1, i + 1] } } } const binarySearch = function(array, target) { let low = 0 let high = array.length - 1 while (low <= high) { let mid = ~~((low + high) / 2) if (array[mid] < target) { low = mid + 1 } else if (array[mid] > target) { high = mid - 1 } else { return mid } } return NOT_FOUND }
|