Cuối Tuần Mua Sắm Khuyến Mãi

Mô tả

Chủ cửa hàng tạp hóa bác Ba đang chuẩn bị cho chương trình khuyến mãi cuối tuần. Bác xếp các mặt hàng thành một dãy dài trên kệ. Mỗi mặt hàng có một mức giá tiền nhất định.

Để nhận được mã giảm giá của chương trình, khách hàng phải chọn một nhóm các mặt hàng xếp liên tiếp nhau trên kệ sao cho tổng giá tiền của nhóm đó lớn hơn hoặc bằng mức threshold S do bác Ba đặt ra. Tất nhiên, khách hàng thì luôn muốn mua càng ít hàng càng tốt để đỡ tốn sức mang, nhưng vẫn phải đủ điều kiện nhận mã giảm giá.

Hãy giúp một khách hàng tìm xem số lượng mặt hàng ít nhất mà họ cần lấy từ kệ (theo thứ tự liên tiếp) để đạt được tổng giá tiền đúng bằng S hoặc hơn. Nếu không có nhóm mặt hàng nào thỏa mãn, hãy trả về 0.

Đầu vào

• Một mảng số nguyên prices thể hiện giá tiền của từng mặt hàng trên kệ theo thứ tự.
• Một số nguyên S là tổng mức giá tiền tối thiểu để nhận khuyến mãi.

Đầu ra

• Trả về một số nguyên duy nhất là số lượng mặt hàng liên tiếp ít nhất cần lấy. Nếu không khả thi, trả về 0.

Ràng buộc

• 1 <= prices.length <= 10^5
• 1 <= prices[i] <= 10^4
• 1 <= S <= 10^9

Ví dụ

Ví dụ 1:

• Đầu vào: prices = [2, 3, 1, 2, 4, 3], S = 7
• Đầu ra: 2
• Giải thích: Nhóm mặt hàng [4, 3] ở cuối có tổng là , đúng bằng mức khuyến mãi và chỉ cần lấy mặt hàng. Không có nhóm liên tiếp nào ngắn hơn đạt tổng từ trở lên.