#167 Two Sum II - Input array is sorted (有圖)

用 Two pointer 方向想會比單純用 Array Method 效能好很多

LeetCode

Given an array of integers that is already sorted in ascending order, 
find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, 
where index1 must be less than index2.

Note:

Your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution and you may not use the same element twice.

inpput: 給一數字陣列跟 target 數字
output: 找出哪兩個 index 的值相加等於 target, index1 一定比 index 2 前面

Example:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

 /**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(num, target) {}

怎麼解

Two pointer 直接翻譯就是兩個指針(廢話)，以這題來說就是 pointer 跟 ind，我們來想一下題目，題目說已經按照大小排好了

• num[pointer] + num[ind] < targer，兩個總和若太小則 pointer ++，讓他總和變大

• num[pointer] + num[ind] > targer，兩個總和若太大 ind -- ，讓他總和變小

var twoSum = function(numbers, target) {
    let pointer = 0;
    let len = numbers.length
    let ind = len - 1
 
    while( target !== numbers[ind] + numbers[pointer]){
        target > numbers[ind] + numbers[pointer] ? pointer ++ : ind --;
    }
       
    return [pointer+1, ind+1];
    
    let L = 0
    let R = numbers.length - 1
    while(L<R){
        if(numbers[L] + numbers[R] === target){
          return [L+1, R+1]    
        }
        
        if(target-numbers[L] < numbers[R]){
            R--
        } else {
            L++
        }
    }
    
    return [-1, -1]
};