Hướng dẫn giải của Truy tìm
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tác giả:
hieubodoi
Với bài này chúng ta sẽ áp dụng một chút mảng cộng dồn + map.
Ta xây dựng được mảng cộng dồn pre và lưu từng giá trị của mảng pre vào map.
Ta có công thức tính tổng 1 đoạn liên tiếp bằng mảng cổng dồn : pre[j] - pre[i] = x;
Ta đã có x và duyệt lần lượt j, với mỗi j kiểm tra xem trong map đã có j hay chưa, nếu có rồi thì ans = max(ans, j - i);
Độ phức tạp : O(nlog(n))
Bình luận