AveragePair

找出平均對等數

const arr = [-11, 0, 1, 2, 3, 9, 14, 17, 21];
const average = 1.5;

// O(n^2)
const averagePair = (arr, average) => {
    const result = [];
    for (let i = 0; i <= arr.length; i++) {
        for (let j = 0; j <= arr.length; j++) {
            const currentItem = arr[i];
            const loopItem = arr[j];
            // arr是被排序過的且不重複數組, 所已loopItem只能大於currentItem才不會重複
            if ((currentItem + loopItem) / 2 === average && loopItem > currentItem) {
                result.push([currentItem, loopItem]);
            }
        }
    }
    return result;
};

// [ [ -11, 14 ], [ 0, 3 ], [ 1, 2 ] ]
console.log(averagePair(arr, average));

透過此方法雖然能找到答案,但是複雜度為O(N^2),透過Pointer優化此演算法

Pointerc和counter一樣是優化複雜度的一個方法,他們並不是一個正式的名稱

只有在sorted array情況下可以使用,找出最左邊和最右邊數字是否等於要找的值,若超過則代表直過大右邊直要遞減,若加總值小於則代表過小左邊要遞增,若等於代表找到該值,左右值分別增減尋找下個符合條件

const arr = [-11, 0, 1, 2, 3, 9, 14, 17, 21];
const average = 1.5;

const averagePair = (arr, average) => {
    let left = 0;
    let right = arr.length - 1;
    const result = [];
    while (right > left) {
        const firstItem = arr[left];
        const lastItem = arr[right];
        const current_average = (firstItem + lastItem) / 2;
        if (current_average > average) {
            right--;
        } else if (current_average < average) {
            left++;
        } else if (current_average === average) {
            result.push([firstItem, lastItem]);
            right--;
            left++;
        }
    }
    return result;
};

console.log(averagePair(arr, average));

leetcode 2108. Find First Palindromic String in the Array: https://leetcode.com/problems/find-first-palindromic-string-in-the-array/

Subsequence

subsequence是判斷比對字串順序是否符合比對的字串

const subsequence = (subStr, str) => {
    const subStrLength = subStr.length;
    const strLength = str.length;
    let subPointer = 0;
    let pointer = 0;
    while (pointer < strLength) {
        if (subStr[subPointer] === str[pointer]) {
						// 比對string條件符合時pointer各++
            subPointer++;
            pointer++;
        } else {
						// 不等於時比對的pointer++
            pointer++;
        }
    }
    // 如果subPointer的長度符合代表全部都跑完則回傳true
    return subPointer === subStrLength;
};

console.log(subsequence('book', 'brooklyn')); // true
console.log(subsequence('hello', 'hello Dear')); // true
console.log(subsequence('abc', 'bac')); // false
console.log(subsequence('abc', 'abc')); // true