หา Max Slice ของอาร์เรย์ | JavaScript

สมมติว่าเราต้องเขียนฟังก์ชันรับอาร์เรย์ คืน slice สูงสุดของอาร์เรย์ที่มีตัวเลขไม่เกินสองตัวที่ต่างกัน หากสังเกตดีๆ ปัญหานี้เกี่ยวกับการตรวจสอบซับอาร์เรย์ที่เสถียรและวนลูปผ่านอาร์เรย์ต้นทาง

ดังนั้น อัลกอริทึม Sliding Window เหมาะสมมาก โค้ดแก้ปัญหาด้วย Sliding Window

ตัวอย่าง

const arr = [1, 1, 1, 2, 2, 2, 1, 1, 2, 2, 6, 2, 1, 8, 1, 1 ,1 ,1, 8, 1, 1, 8, 8];
const map = {
  length: 0
};
let required = [];
for(start = 0, end = 0; end <= arr.length; ){
  if(map.length > 2){
    if(map[arr[start]] === 1){
      delete map[arr[start]];
      map.length --;
    }else{
      map[arr[start]]--;
    };
    start++;
  }else{
    if(end - start > required.length){
      required = arr.slice(start, end);
    };
    if(map[arr[end]]){
      map[arr[end]]++;
    }else{
      map[arr[end]] = 1;
      map.length++;
    }
    end++;
  }
}
console.log(required);

เราเก็บ map นับจำนวนตัวเลขที่ต่างกันในแต่ละจุด และเปรียบเทียบความยาวซับอาร์เรย์ที่ยาวที่สุดในแต่ละรอบ เมื่อจำนวนตัวเลขที่ต่างกันเกิน 2 เราเลื่อนอาร์เรย์ไปขวาค้นหาซับอาร์เรย์เสถียรถัดไป

ผลลัพธ์

ผลลัพธ์ในคอนโซลจะเป็น

[ 1, 8, 1, 1, 1, 1, 8, 1, 1, 8, 8 ]