Chương trình đếm số danh sách con độ dài k có trung bình lớn hơn hoặc bằng mục tiêu trong Python

Mô tả bài toán

Cho danh sách nums, số nguyên k và target. Đếm số danh sách con liên tiếp độ dài k có giá trị trung bình ≥ target.

Ví dụ: nums = [1, 10, 5, 6, 7], k = 3, target = 6 → đầu ra 2 (sublist [1,10,7] trung bình 6, [10,5,6] trung bình 7).

Giải thuật (Cửa sổ trượt)

1. Chuyển điều kiện trung bình ≥ target thành tổng ≥ target * k.
2. Khởi tạo sum = 0, ans = 0.
3. Duyệt qua chỉ số i và giá trị n:
   • Nếu i >= k: trừ nums[i - k] khỏi sum.
   • Cộng n vào sum.
   • Nếu i >= k - 1 và sum >= target * k: tăng ans.
4. Trả về ans.

Ví dụ mã Python

class Solution:
    def solve(self, nums, k, target):
        target *= k
        sum = 0
        ans = 0
        for i, n in enumerate(nums):
            if i >= k:
                sum -= nums[i - k]
            sum += n
            if i >= (k - 1):
                if sum >= target:
                    ans += 1
        return ans

ob = Solution()
nums = [1, 10, 5, 6, 7]
k = 3
target = 6
print(ob.solve(nums, k, target))

Đầu vào

[1, 10, 5, 6, 7], 3, 6

Đầu ra

2