Cho mảng số nguyên nums, đếm số cách tách hợp lệ tại chỉ số i khi tổng của nums[0..i] lớn hơn hoặc bằng tổng của nums[i+1..n-1], và mỗi bên có ít nhất một phần tử.

Bài học kỹ thuật. Hai "tổng" trong bài này thực chất là một: tổng toàn phần. Một khi tính được total, nửa phải chỉ là total - left. Đây cũng là cách ta thu gọn quét thành một tổng chạy trong hệ thống thực — một tổng lũy tiến là cấu trúc dữ liệu rẻ nhất mà bạn có thể duy trì.

Ý tưởng

Hai giá trị thay đổi khi điểm chia di chuyển về phía trước: leftSum (nửa trái) và rightSum (nửa phải). Nhưng chúng không độc lập — dù tách ở đâu, leftSum + rightSum luôn bằng tổng toàn phần của mảng.

Vậy câu hỏi thực sự là: cập nhật leftSum rẻ như thế nào khi i tăng, và suy ra rightSum mà không cần quét lại?

Cách tiếp cận

  1. Tính totalSum một lần.
  2. Quét i từ 0 đến n - 2:
    • leftSum += nums[i]
    • rightSum = totalSum - leftSum
    • nếu leftSum >= rightSum, đếm thêm một cách tách.
function waysToSplitArray(nums: number[]): number {
  const totalSum = nums.reduce((sum, num) => sum + num, 0);
  let leftSum = 0;
  let result = 0;
 
  for (let i = 0; i < nums.length - 1; i++) {
    leftSum += nums[i];
    const rightSum = totalSum - leftSum;
    if (leftSum >= rightSum) {
      result++;
    }
  }
 
  return result;
}

Độ phức tạp

  • Thời gian: O(n) — một lần duyệt sau phép reduce ban đầu.
  • Bộ nhớ: O(1) — một nhúm số.

Bài học

Khi bài toán đưa cho bạn hai đại lượng luôn cộng lại bằng một hằng số, hãy tính hằng số và suy ra một đại lượng từ đại lượng kia. Bạn thường sẽ biến một vòng quét kép O(n²) thành một lần duyệt sạch sẽ.