ตรวจสอบว่าแบ่งอาร์เรย์เป็น Subsequence ติดกันได้หรือไม่ใน JavaScript

ปัญหา

เราต้องเขียนฟังก์ชัน JavaScript ที่รับอาร์เรย์ของจำนวนเต็มที่เรียงแล้ว arr เป็นอาร์กิวเมนต์เดียว

ฟังก์ชันควรคืนค่า true ก็ต่อเมื่อเราสามารถแบ่งอาร์เรย์เป็น 1 หรือหลาย subsequence ที่แต่ละ subsequence ประกอบด้วยจำนวนเต็มติดกันและมีความยาวอย่างน้อย 3 มิฉะนั้น false

ตัวอย่างเช่น หากอินพุตคือ

Input

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

Output

const output = true;

คำอธิบายผลลัพธ์

เราสามารถแบ่งได้สอง subsequence ติดกัน:

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));

ผลลัพธ์

true