Một mảng được gọi là điều hòa nếu chênh lệch giữa giá trị lớn nhất và nhỏ nhất đúng bằng 1. Cho nums, trả về độ dài của dãy con điều hòa dài nhất (các phần tử không cần liên tiếp — nhưng thứ tự và số lượng nhân bản được giữ nguyên theo mảng gốc).

Bài học kỹ thuật. "Dãy con, không phải dãy con liên tiếp" nghĩa là ta chỉ quan tâm số lượng, không phải vị trí. Bất cứ khi nào bài toán hỏi về việc một giá trị xuất hiện bao nhiêu lần thay vì xuất hiện ở đâu, hãy nghĩ đến bản đồ tần suất trước — nó biến một tìm kiếm hai chiều thành vài phép tra cứu O(1).

Ý tưởng

Nếu giá trị lớn nhất và nhỏ nhất của dãy con chênh lệch đúng 1, thì dãy con chỉ có thể chứa các giá trị v và v + 1 (với một v nào đó). Độ dài của nó chỉ đơn giản là:

count(v) + count(v + 1)

Vậy bài toán thu gọn thành: với mỗi giá trị trong mảng, có giá trị lân cận v ± 1 hay không? Nếu có, tổng count(v) + count(v + 1) lớn nhất có thể là bao nhiêu?

Cách tiếp cận

  1. Đếm mọi giá trị bằng một Map.
  2. Với mỗi giá trị phân biệt num, kiểm tra xem num + 1 có tồn tại không.
  3. Theo dõi giá trị lớn nhất của freq[num] + freq[num + 1].

Chỉ kiểm tra num + 1 (không kiểm tra num - 1) để tránh đếm mỗi cặp hai lần.

function findLHS(nums: number[]): number {
  const freq = new Map<number, number>();
  let answer = 0;
 
  for (const num of nums) {
    freq.set(num, (freq.get(num) ?? 0) + 1);
  }
 
  for (const [num, count] of freq) {
    const next = freq.get(num + 1);
    if (next !== undefined) {
      answer = Math.max(answer, count + next);
    }
  }
 
  return answer;
}

Độ phức tạp

  • Thời gian: O(n) — một lần đếm, một lần duyệt các khóa phân biệt.
  • Bộ nhớ: O(n) — cho bản đồ tần suất.

Bài học

"Dãy con" là một gợi ý: thứ tự không quan trọng, nên số lượng mới quan trọng. Ngay khi bạn chuyển bài toán thành tần suất, hash map gần như luôn thắng. Đó cũng là bản năng đằng sau caching — tính trước câu trả lời cho câu hỏi đắt nhất (giá trị v xuất hiện bao nhiêu lần?) và trả lời trong O(1).