0724. Find Pivot Index
- Nhãn: Mảng, Tổng tiền tố
- Độ khó: Dễ
Đề bài
Mô tả: Cho một mảng .
Yêu cầu: Tìm vị trí “trung tâm” trong mảng, nghĩa là vị trí mà tổng các phần tử bên trái bằng tổng các phần tử bên phải. Nếu không tìm thấy, trả về .
Giải thích:
- .
- .
Ví dụ:
- Ví dụ 1:
- Ví dụ 2:
Ý tưởng
Ý tưởng 1: Duyệt hai lần
Duyệt hai lần, lần đầu tiên tính tổng của toàn bộ mảng. Lần thứ hai duyệt để tìm vị trí mà tổng của các phần tử bên trái bằng một nửa tổng của toàn bộ mảng.
Ý tưởng 1: Cài đặt
Ý tưởng 1: Độ phức tạp
- Độ phức tạp thời gian: . Độ phức tạp thời gian của hai vòng lặp là , .
- Độ phức tạp không gian: .