iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 28
2

會提到 Two Pointer,除了 LeetCode 有一個類別是 "Two Pointer",另外認為很適合拿來入門刷題。因為剛開始刷題總是很容易朝著 Big O(n²) 方向想,例如以下

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

又或是

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

但使用 Two pointer 方向想,通常可以讓時間複雜度保持在 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:

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.
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 方向想吧

https://ithelp.ithome.com.tw/upload/images/20190929/201064261b44zfUicD.jpg
Two pointer 直接翻譯就是兩個指針(廢話),以這題來說就是 pointer 跟 ind,我們來想一下題目,題目說已經按照大小排好了

  • num[pointer] + num[ind] < targer,兩個總和若太小則 pointer ++,讓他總和變大
    https://ithelp.ithome.com.tw/upload/images/20190929/20106426qLDlg0DgLr.jpg
  • num[pointer] + num[ind] > targer,兩個總和若太大 ind -- ,讓他總和變小
    https://ithelp.ithome.com.tw/upload/images/20190929/20106426WkhUaeNKih.jpg

完整程式碼

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

最後幾天真的好難撐啊!! 尤其是假日真的是門檻。
剩兩天了啊~~ 加油加油

如有錯誤或需要改進的地方,拜託跟我說。
我會以最快速度修改,感謝您

上一篇
[LeetCode #322] Dynamic Programming
下一篇
[有趣面試題] 網頁效能問題改善之 Debounce & Throttle
系列文
前端工程師用 javaScript 學演算法32

尚未有邦友留言

立即登入留言