1. The subject

Given an array of integers in non-decreasing order numbers, find two numbers that add up to the target number.

The function should return the subscript values of these two numbers as an array of integers of length 2. The subscript of numbers starts at 1, so the answer array should be 1 <= answer[0] < answer[1] <= numbers. Length.

You can assume that each input corresponds to a unique answer, and you can’t reuse the same elements.

Example 1:

Numbers = [2,7,11,15] target = 9 output: [1,2] So index1 = 1, index2 = 2.Copy the code

Example 2:

Numbers = [2,3,4] target = 6Copy the code

Example 3:

Numbers = [-1,0] target = -1Copy the code

 

Tip:

  • 2 <= numbers.length <= 3 * 104
  • -1000 <= numbers[i] <= 1000
  • Numbers is arranged in non-decreasing order
  • -1000 <= target <= 1000
  • There is only one valid answer
  • Passes 345,963 submissions 58

2. The preface

This problem can be solved using 1. Sum of two numbers, using O(n2) time complexity and O(1) space complexity violence, or using hash tables using O(n) time complexity and O(n) space complexity. But these two solutions are for unordered arrays and do not take advantage of the ordered nature of the input array. By taking advantage of the ordered nature of the input array, a better solution of time complexity and space complexity can be obtained.

3. Binary search

One number is fixed and the other digit is found by dichotomy

/ * * *@param {number[]} numbers
 * @param {number} target
 * @return {number[]}* /
 var twoSum = function(numbers, target) {
  const len = numbers.length
  for(let i = 0; i < len - 1; i++) {
    let left = i + 1
    let right = len - 1
    const needNum = target - numbers[i]
    while(left <= right) {
      const mid = (left + right) >> 1
      if(numbers[mid] === needNum) {
        return [i + 1, mid + 1]}else if(numbers[mid] < needNum) {
        left = mid + 1
      } else if(numbers[mid] > needNum) {
        right = mid - 1}}}};Copy the code

Complexity analysis:

  • Time complexity: O(nlogn)
  • Space complexity: O(1)

4. Double pointer

We start with two Pointers to the first and last element positions. Each time the sum of the two elements pointed to by the two Pointers is evaluated and compared with the target value. If the sum of the two elements equals the target value, a unique solution is found. If the sum of the two elements is less than the target value, move the left pointer one bit to the right. If the sum of the two elements is greater than the target value, the right pointer is moved one bit to the left. After you move the pointer, repeat until you find the answer.

/ * * *@param {number[]} numbers
 * @param {number} target
 * @return {number[]}* /
 var twoSum = function(numbers, target) {
  let left = 0,right = numbers.length - 1
  while(left < right) {
    const sum = numbers[left] + numbers[right]
    if(sum > target) {
      right--
    } else if(sum < target) {
      left++
    } else {
      return [left + 1, right + 1]}}};Copy the code

Complexity analysis

  • Time complexity: O(n), where nn is the length of the array. The total number of moves of the two Pointers is at most N.
  • Space complexity: O(1).