若想找到兩個array中重複的值,直覺的寫法可以使用兩個for loop

const arr1 = [1, 2, 3];
const arr2 = [5, 16, 1, 3];

const fn = (arr1, arr2) => {
    let result = [];
    for (let i = 0; i < arr1.length; i++) {
        for (let k = 0; k < arr2.length; k++) {
            if (arr1[i] === arr2[k]) result.push(arr1[i]);
        }
    }
    return result;
};
// result: [1, 3]
console.log(fn(arr1, arr2));

但這種方式的BIG O為n^2

1. counter為一種演算法的使用技巧,使用object計算排序出現過的數字

// counter
const counter = (arr1, arr2) => {
    const arr = [...arr1, ...arr2];
    const obj = {};
    const result = [];
    for (let i = 0; i < arr.length; i++) {
        if (!obj[arr[i]]) {
            // 找不到值時代表沒有,記錄一次
            obj[arr[i]] = 1;
        } else {
            // obj裡有該值, ++
            obj[arr[i]] += 1;
        }
    }
    for (let property in obj) {
        obj[property] > 1 && result.push(property);
    }
    return result;
};

console.log('counter result : ', counter(arr1, arr2));

透過counter這個幾巧,將原本n^2的BIG O調整為2n ⇒ O(n)