Tìm x, y thỏa mãn điều kiện về tổng đoạn con từ x -> y bằng k

[bubabua (Huy Quang)]

Trên một đoạn đường trong một khu phố có n ngôi nhà liên tiếp được đánh số từ 0 đến n-1 .

Cho mảng a chứa số người trong từng ngồi nhà trong đó ngôi nhà thứ i có a[i] người.

Cho một số nguyên dương k . Hải cần tìm ra hai chỉ số x và y thỏa mãn:

• Tổng số người dân từ ngồi nhà thứ x đến ngôi nhà thứ y là k người.
• Nếu có nhiều đoạn có tổng là k người thì đoạn x đến y phải ít ngôi nhà nhất.
• Nếu có nhiều đoạn có tổng là k người và đoạn x đến y ít ngôi nhà nhất thì đưa ra đoạn chỉ số x nhỏ nhất.
• Nếu không có đoạn nào thõa mãn đưa ra -1 .

Ví dụ:

• Với a = [1,2,3,6,7,6], k=6 thì town(a,k) = [3,3].
  Giải thích:
  • Có nhiều đoạn (x,y) có tổng số người trong nhà bằng k là: (0,2), (3,3), (5,5), nhưng hai đoạn (3,3) và (5,5) có ít ngôi nhà hơn đoạn (0,2) .
  • Với hai đoạn (3,3) và (5,5) thì đoạn (3,3) có chỉ số x nhỏ hơn.
• Với a = [1,2,3], k=4 thì town(a,k) = [-1].

Ai giúp e bài này với ạ

[VuVanChung]

Có cần yêu cầu về thời gian không em? Nếu không yêu cầu thời gian và bộ nhớ thì em có thể làm nó trong O(n^2) thời gian và O(n) bộ nhớ. Em dùng mảng Sum để lưu tổng các số từ 0 tới i, nghĩa là

sum[i] = a[0] + a[1] + … + a[i]

Sau đó em muốn tính tổng từ i tới j thì lấy sum[j] - sum[i] thôi

[bubabua (Huy Quang)]

có yêu cầu về thời gian ạ