1. 预处理
      1. j从新旧子节点头部开始处理相同key节点
      2. 两指针从两子节点尾开始处理相同节点
    2. 新节点如果已处理完，旧节点没有处理完，卸载旧节点
    3. 旧节点已处理完，新节点没有处理完，逐个插入新节点

    4. 新旧节点都没处理完

      1. 找到新节点对应的旧节点索引，如[2,3,1,-1]
      2. -1代表新节点需要插入
      3. 计算最长递增子序列
      4. 从新节点尾部往前遍历

      5. 如果不在最长子序列中，说明需要将当前节点的DOM往后移、

        1. function patchKedChildren3(n1, n2, container) {
        2. const oldChildren = n1.children
        3. const newChildren = n2.children
        4. //预处理
        5. let j = 0
        6. let oldVNode = oldChildren[j]
        7. let newVNode = newChildren[j]
        8. while (newVNode.key === oldVNode.key) {
        9. patch(oldVNode, newVNode, container)
        10. j++
        11. oldVNode = oldChildren[j]
        12. newVNode = newChildren[j]
        13. }
        14. let oldEndIndex = oldChildren.length - 1
        15. let newEndIndex = newChildren.length - 1
        16. oldVNode = oldChildren[oldEndIndex]
        17. newVNode = newChildren[newEndIndex]
        18. while (newVNode.key === oldVNode.key) {
        19. patch(oldVNode, newVNode, container)
        20. oldEndIndex--
        21. newEndIndex--
        22. oldVNode = oldChildren[oldEndIndex]
        23. newVNode = newChildren[newEndIndex]
        24. }
        25. //如果旧子节点已处理结束，新子节点没有，则新增
        26. if (oldEndIndex < j && newEndIndex >= j) {
        27. const anchorIndex = newEndIndex + 1
        28. const anchor =
        29. anchorIndex < newChildren.length ? newChildren[anchorIndex].el : null
        30. while (j <= newEndIndex) {
        31. patch(null, newChildren[j], container, anchor)
        32. j++
        33. }
        34. //如果新子节点已处理结束，旧子节点没有，则卸载全部未处理旧子节点
        35. } else if (newEndIndex < j && oldEndIndex >= j) {
        36. while (j <= oldEndIndex) {
        37. unmount(oldChildren[j++])
        38. }
        39. //处理交换位置
        40. } else {
        41. const count = newEndIndex - j + 1
        42. const source = new Array(count)
        43. source.fill(-1)
        45. const indexMap = {}
        46. const pos = 0
        47. const newStart = j
        48. const oldStart = j
        49. //indexMap存储形式{key,index}
        50. for (let i = newStart; i <= newEndIndex; i++) {
        51. indexMap[newChildren[i].key] = i
        52. }
        53. let patched = 0
        54. let move = false
        55. for (let i = oldStart; i <= oldEndIndex; i++) {
        56. const oldVNode = oldChildren[i]
        57. if (patched > count) {
        58.   const k = indexMap[oldVNode.key]
        59.   if (k) {
        60.     const newVNode = newChildren[ind]
        61.     patched++
        62.     patch(oldVNode, newVNode, container)
        63.     source[k - newStart] = i
        64.     if (k < pos) {
        65.       move = true
        66.     } else {
        67.       pos = k
        68.     }
        69.   } else {
        70.     unmount(oldVNode)
        71.   }
        72. } else {
        73.   unmount(oldVNode)
        74. }
        75. }
        76. //递增子序列，不需移动
        77. const seq = getSequence(source)
        78. //s指向递增子序列最后
        79. let s = seq.length - 1
        80. //i指向需要移动的子节点最后
        81. let i = count - 1
        82. for (i; i >= 0; i--) {
        83. //等于-1说明是新增需要插入
        84. if (source[i] === -1) {
        85.   //children中的位置
        86.   const pos = i + newStart
        87.   const anchorIndex = pos + 1
        88.   const anchor = newChildren[anchorIndex]
        89.     ? newChildren[anchorIndex].el
        90.     : null
        91.   patch(null, newChildren[pos], container, anchor)
        92.   //i比当前seq指针位置小，说明i处的新子节点需要移到最后
        93. } else if (i !== seq[s]) {
        94.   if (i < seq[s]) {
        95.     const pos = i + newStart
        96.     const anchorIndex = pos + 1
        97.     const anchor = newChildren[anchorIndex]
        98.       ? newChildren[anchorIndex].el
        99.       : null
        100.     insert(newChildren[pos].el, container, anchor)
        101.   }
        102.   //节点一样s上移一位
        103. } else {
        104.   s--
        105. }
        106. }
        107. }
        108. }