[LeetCode 75/Sliding Window] 643 - Maximum Average Subarray 1 / 1456 - Maximum Number of Vowels in a Substring of Given Length / 1004 - Max Consecutive Ones 3 / 1493 - Longest Subarray of 1's After Deleting One Element (Java)

643 - Maximum Average Subarray 1

---

풀이

길이가 k인 연속된 부분 배열의 평균 최대

-> 합이 최대여야 함

 

처음 k개 합 계산 -> 한 칸씩 이동하면서 새로운 값 더하고 빠지는 값 빼기

• `sum += nums[i]`
• `sum -= nums[i]`

---

코드

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int n = nums.length;

        long sum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }

        long maxSum = sum;
        for (int i = k; i < n; i++) {
            sum += nums[i];
            sum -= nums[i - k];
            maxSum = Math.max(maxSum, sum);
        }

        return (double) maxSum / k;
    }
}

---

1456 - Maximum Number of Vowels in a Substring of Given Length

---

풀이

길이가 k인 연속된 부분 배열의 모음 개수 최대 

 

처음 모음 개수 계산 -> 한 칸씩 이동하면서 새 문자 모음이면 +1 / 빠지는 문자 모음이면 -1

• `isVowel(s.charAt(i))` -> `cnt++`
• `isVowel(s.charAt(i - k))` -> `cnt--`

---

코드

class Solution {
    static boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i'
            || c == 'o' || c == 'u';
    }

    public int maxVowels(String s, int k) {
        int n = s.length();
        int cnt = 0;

        for (int i = 0; i < k; i++) {
            if (isVowel(s.charAt(i))) cnt++;
        }
        
        int max = cnt;
        for (int i = k; i < n; i++) {
            if (isVowel(s.charAt(i))) cnt++;
            if (isVowel(s.charAt(i - k))) cnt--;

            max = Math.max(max, cnt);

            if (max == k) return k;
        }

        return max;
    }
}

---

1004 - Max Consecutive Ones 3

---

풀이

0을 최대 k까지 뒤집을 수 있을 때 가장 긴 연속 1 길이

-> 윈도우 안에 0이 k개 이하인 가장 긴 구간

 

윈도우 오른쪽으로 확장

• 뒤집어야 할 0 개수(`cnt`) > 최대 뒤집을 수 있는 횟수(k) -> 윈도우 불가능한 상태 => 왼쪽 줄여야 함
  • 왼쪽 원소가 0이었다면 0 개수도 줄여줌
• 최대 길이 갱신: `max = Math.max(max, rt - lt + 1)`

---

코드

class Solution {
    public int longestOnes(int[] nums, int k) {
        int lt = 0;
        int cnt = 0;
        int max = 0;

        for (int rt = 0; rt < nums.length; rt++) {
            if (nums[rt] == 0) cnt++;

            while (cnt > k) {
                if (nums[lt] == 0) cnt--;
                lt++;
            }

            max = Math.max(max, rt - lt + 1);
        }

        return max;
    }
}

---

1493 - Longest Subarray of 1's After Deleting One Element

---

풀이

원소 1개 삭제한 뒤 가장 긴 연속 1 길이

-> 윈도우 안에 0이 최대 1개인 가장 긴 길이 - 삭제 1개

 

윈도우 오른쪽으로 확장

• 0 개수(`cnt`) > 1 -> 윈도우 불가능한 상태 => 왼쪽 줄여야 함
  • 왼쪽 원소가 0이었다면 0 개수도 줄여줌
• 최대 길이 갱신: `maxLen = Math.max(maxLen, rt - lt + 1)`

반드시 1개 삭제해야 함: `maxLen - 1`

---

코드

class Solution {
    public int longestSubarray(int[] nums) {
        int lt = 0;
        int cnt = 0;
        int maxLen = 0;

        for (int rt = 0; rt < nums.length; rt++) {
            if (nums[rt] == 0) cnt++;

            while (cnt > 1) {
                if (nums[lt] == 0) cnt--;
                lt++;
            }

            maxLen = Math.max(maxLen, rt - lt + 1);
        }

        return maxLen - 1;
    }
}

---

출처

LeetCode 75 - Study Plan - LeetCode