[LeetCode 75] Easy - 643. Maximum Average Subarray I

643. Maximum Average Subarray I

 

You are given an integer array nums consisting of n elements, and an integer k.

Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10-5 will be accepted.

 

Example 1:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanation: Maximum average is (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75

Example 2:

Input: nums = [5], k = 1
Output: 5.00000

 

Constraints:

• n == nums.length
• 1 <= k <= n <= 10^5
• -10^4 <= nums[i] <= 10^4

 

문제 조건

 

이 문제는 주어진 배열 nums에서 길이가 정확히 k인 연속적인 부분 배열(subarray) 중 평균이 최대가 되는 값을 찾는 문제입니다.

---

문제 조건

1. 입력:
   • nums: 정수 배열 (1≤n≤1051 \leq n \leq 10^51≤n≤105).
   • k: 부분 배열의 길이 (1≤k≤n1 \leq k \leq n1≤k≤n).
2. 출력:
   • 최대 평균 값을 반환 (오차<10−5\text{오차} < 10^{-5}오차<10−5).
3. 제약:
   • 각 숫자 nums[i]nums[i]nums[i]는 [−104,104][-10^4, 10^4][−104,104] 범위에 있음.

---

풀이 접근

1. 브루트 포스 (비효율적)

• 모든 길이 k의 부분 배열의 합을 계산하여 평균을 구합니다.
• 시간 복잡도는 O(n⋅k)O(n \cdot k)O(n⋅k)으로, nnn이 클 때 비효율적입니다.

2. 슬라이딩 윈도우 (효율적)

• 길이가 k인 부분 배열의 합을 계산하는 데 슬라이딩 윈도우 기법을 사용합니다.
• 첫 번째 부분 배열의 합을 계산한 후, 다음 윈도우로 이동하면서:
  • 새로 추가되는 값은 더하고,
  • 이전 윈도우의 첫 번째 값을 빼는 방식으로 업데이트.
• 시간 복잡도는 O(n)O(n)O(n)으로 효율적입니다.