可以在 JavaScript 中将数组拆分为连续的子序列

Z时代
2024-01-10
分类：综合

问题

我们需要编写一个 JavaScript 函数，它接受一个有序整数数组 arr 作为第一个也是唯一的参数。

当且仅当我们可以将数组拆分为 1 个或多个子序列，使得每个子序列由连续整数组成并且长度至少为 3 时，我们的函数才应该返回 true，否则返回 false。

例如，如果函数的输入是

输入

const arr = [1, 2, 3, 3, 4, 5];

输出

const output = true;

输出说明

我们可以将它们分成两个连续的子序列 -

1, 2, 3

3, 4, 5

示例

以下是代码 -

const arr = [1, 2, 3, 3, 4, 5];
const canSplit = (arr = []) => {
   const count = arr.reduce((acc, num) => {
      acc[num] = (acc[num] || 0) + 1
      return acc
   }, {})
   const needed = {}
   for (const num of arr) {
      if (count[num] <= 0) {
         continue
      }
      count[num] -= 1
      if (needed[num] > 0) {
         needed[num] -= 1
         needed[num + 1] = (needed[num + 1] || 0) + 1
      } else if (count[num + 1] > 0 && count[num + 2]) {
         count[num + 1] -= 1
         count[num + 2] -= 1
         needed[num + 3] = (needed[num + 3] || 0) + 1
      } else {
         return false
      }
   }
   return true
}
console.log(canSplit(arr));