[Sliding Window Fixed Size] 1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold

1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold

 

✅ 문제 요약 (LeetCode 1343)

• 정수 배열 arr, 정수 k, threshold가 주어짐
• 크기가 k인 연속된 부분 배열(subarray) 중,
  평균이 threshold 이상인 경우의 개수를 리턴

---

✅ 핵심 아이디어

• 슬라이딩 윈도우 크기 = k
• 평균 ≥ threshold → sum ≥ threshold * k 로 변환해서 비교하면 정수만 다룰 수 있음
• 슬라이딩 윈도우 방식으로 한 칸씩 이동하면서 합을 업데이트

---

✅ 최적 풀이 (Python, O(n) 시간)

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        # 크기가 k 인 subarry(연속행렬)의 평균 >= threshold 인 개수 찾기
        len_arr = len(arr)
        res = 0

        windowSum = sum(arr[:k]) # 초기 윈도우
        if windowSum >= k*threshold:
            res +=1
            
        for r in range(k,len_arr):
            # + arr[r] 새 요소(오른쪽 값) 추가
            # - arr[r-k] 제일 왼쪽 값 제거
            windowSum = windowSum+arr[r]-arr[r-k]
            if windowSum >= threshold*k:
                res+=1

        return res

 

✅ 시간 & 공간 복잡도

• 시간복잡도: O(n) (arr 한 번만 순회)
• 공간복잡도: O(1) (슬라이딩 윈도우 합만 유지)