การหาคู่สมาชิกในอาร์เรย์ที่ต่างกันไม่เกิน m และ index ต่างกันไม่เกิน n ใน JavaScript

บทความนี้สาธิตการหาว่ามีคู่สมาชิก (a1, a2) ในอาร์เรย์ที่ |a1 - a2| <= m และ |index1 - index2| <= n หรือไม่

ตัวอย่างโค้ด

const arr = [1, 2, 3, 1, 7, 8];

const findSpecialElements = (arr = [], m, n) => {
  const map = arr
    .map((el, ind) => ({ el, ind }))
    .sort((a, b) => a.el - b.el);
  let left = 0;
  let right = 1;
  while (right < map.length) {
    const diff = Math.abs(map[right].el - map[left].el);
    const range = Math.abs(map[right].ind - map[left].ind);
    if (diff <= n && range <= m) {
      return true;
    } else if (diff > n) {
      left++;
    } else if (range > m) {
      right++;
    }
    if (left === right) {
      right++;
    }
  }
  return false;
};

console.log(findSpecialElements(arr, 3, 0));

ผลลัพธ์

true

คำอธิบาย

แปลงอาร์เรย์เป็น array of objects {el, ind} เรียงตามค่า el ใช้ two pointers (left, right) หาคู่ที่ต่างกันไม่เกิน n (ค่า) และ m (index)

หมายเหตุ: พารามิเตอร์ m,n ในโค้ดดูสลับกัน (diff <= n, range <= m) ควรตรวจสอบความหมายพารามิเตอร์