如何获取两个FIFO数组状态的差值，提取头部新增的元素？

实现思路 #

FIFO队列头部新增n个元素时，会同步从尾部移除n个元素，因此新旧数组长度完全一致。我们只需要找到旧数组前缀与新数组后缀完全匹配的最大长度，用数组总长度减去该匹配长度，就是头部新增元素的个数，取新数组前对应个数的元素即可得到结果。

代码实现 #

function getItemsAdded(oldArr, newArr) {
    const arrLength = oldArr.length;
    // 校验长度是否符合FIFO变更规则
    if (arrLength !== newArr.length) return [];

    // 从最长可能的匹配长度倒序查找
    for (let matchLen = arrLength; matchLen >= 0; matchLen--) {
        const newArrStart = arrLength - matchLen;
        let matched = true;
        for (let i = 0; i < matchLen; i++) {
            if (oldArr[i] !== newArr[newArrStart + i]) {
                matched = false;
                break;
            }
        }
        if (matched) {
            return newArr.slice(0, arrLength - matchLen);
        }
    }
    return [];
}

测试验证 #

给出的4组测试用例执行结果完全符合预期：

// Input 1
const arr1 = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'];
const arr2 = ['a', 'b', 'a', 'b', 'c', 'd', 'e', 'f', 'g'];
console.log(getItemsAdded(arr1, arr2)); // [ 'a', 'b' ]

// Input 2
const arr3 = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'];
const arr4 = ['q', 'r', 'a', 'b', 'c', 'd', 'e', 'f', 'g'];
console.log(getItemsAdded(arr3, arr4)); // [ 'q', 'r' ]

// Input 3
const arr5 = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'];
const arr6 = ['a', 'b', 'q', 'a', 'b', 'c', 'd', 'e', 'f'];
console.log(getItemsAdded(arr5, arr6)); // [ 'a', 'b', 'q' ]

// Input 4
const arr7 = ['a', 'b', 'a', 'b', 'c', 'd', 'e', 'f', 'g'];
const arr8 = ['a', 'b', 'a', 'b', 'a', 'b', 'c', 'd', 'e'];
console.log(getItemsAdded(arr7, arr8)); // [ 'a', 'b' ]

内容的提问来源于stack exchange，提问作者Jonathan de Geus