หา Subarray ต่อเนื่องที่มีจำนวน 0 และ 1 เท่ากัน (JavaScript)

ปัญหา

รับอาร์เรย์ไบนารี หา subarray ต่อเนื่องที่มีจำนวน 0 และ 1 เท่ากัน และคืนความยาวสูงสุด

ตัวอย่าง

const arr = [1, 0, 0, 1, 0, 1, 0, 0];

6 ตัวแรก: 1,0,0,1,0,1 (สาม 1 และสาม 0) → ผลลัพธ์ 6

โค้ดตัวอย่าง (Prefix Sum + Hash Map)

const arr = [1, 0, 0, 1, 0, 1, 0, 0]; 
const findMaxLength = (arr = []) => { 
  const { length } = arr; 
  if (length < 2) return 0; 
  const map = new Map(); 
  map.set(0, -1); 
  let sum = 0, max = 0; 
  for (var i = 0; i < length; i++) { 
    sum += arr[i] === 0 ? -1 : 1; 
    if (map.has(sum)) { max = Math.max(max, i - map.get(sum)); } 
    else { map.set(sum, i); } 
  } 
  return max; 
}; 
console.log(findMaxLength(arr));

คำอธิบาย

นับ 0 เป็น -1, 1 เป็น +1 คำนวณ prefix sum เมื่อ sum ซ้ำกัน แสดงว่าระหว่างสองจุดมี 0 และ 1 เท่ากัน

ผลลัพธ์

6