LeetCode - 167. Two Sum II - Input Array Is Sorted

Thoughts:

I choose two pointer to solve this problem,

when I need to compare two values and the array is sorted,

it’s perfect to use two pointer with left and right pointer.

The problem also says that the space complexity must be O(1), this algorithm only need to store the value of two pointers.

The time complexity is O(n) for the iteration.

Thoughts visuzlization:

l is left pointer, and r is right pointer

nums = [2,7,11,15], target = 9

if too big than target, move right pointer to left
if too small than target, move left pointer to right

[2,7,11,15]
 l      r
[2,7,11,15]
 l    r
[2,7,11,15]
 l r

Code:

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

Reference

Original link