Vấn đề:
Cần viết hàm JS nhận mảng nhị phân arr (chỉ 0 và 1). Trả về độ dài mảng con liên tiếp dài nhất có số lượng 0 và 1 bằng nhau.
Ví dụ:
const arr = [1, 0, 0, 1, 0, 1, 0, 0];
Kết quả:
const output = 6;
Giải thích:
6 phần tử đầu: 1,0,0,1,0,1 (ba 1 và ba 0).
Ví dụ
Mã thực hiện:
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; let 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));
Giải thích code:
Coi 0 là -1, 1 là 1, tính tổng prefix. Khi tổng bằng nhau tại hai vị trí, đoạn giữa có số 0 và 1 bằng nhau.
Kết quả
Kết quả in ra console:
6