DAY 28
2
Software Development

## [LeetCode #167] Two Pointer

``````for (var i = 0; i < len - 1; i++) {
for (var j = i + 1; j < len; j++) {
...
}
}
``````

``````for(){
包 map/indexOf/find 這樣基本上都是遍歷兩次 Big O(n²)
}
``````

# 167. Two Sum II - Input array is sorted

``````// Question:
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:

You may assume that each input would have exactly one solution and you may not use the same element twice.
``````
``````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) {
const len = num.length;
for(let i = 0; i< len; i++ ){
var ind = num.indexOf(target - num[i]);
if(ind !== -1 && i !== ind){
return [i + 1, ind + 1].sort( (a,b) => a - b);
}
}
return false;

};
``````

for 一次、indexOf 一次。然後為了題目順序又 sort 一次。時間複雜度已是比 Big O (n²) 還差。難怪解出來是
Runtime: 400 ms, faster than 5.94% of JavaScript online submissions 效能超差

### 用 Two Pointer 方向想吧

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];
};
``````

``````如有錯誤或需要改進的地方，拜託跟我說。

``````