2841. Maximum Sum of Almost Unique Subarray

[zeikar]

Problem link

https://leetcode.com/problems/maximum-sum-of-almost-unique-subarray

Problem Summary

배열과 m, k가 주어질 때 배열의 subarray 중에서 길이가 k이고 중복되지 않는 수가 최소 m개인 개수를 구하는 문제.

Solution

딱 보니 간단한 슬라이딩 윈도우 문제이다.
배열의 처음부터 끝까지 죽 돌면서 길이가 k이고 중복되지 않는 수가 m개가 되도록 체크해주면 된다.

중복되는 수 체크는 map (dict)로 간단하게 할 수 있고 right는 개수 증가, left는 개수 감소를 해주면서 중복되지 않는 수가 몇개인지 계속 체크해주면서 슬라이딩 윈도우를 이동시키면 된다.

코드 자체는 생각보다 길긴 한데 어렵지 않다.

Source Code

from collections import defaultdict
from typing import List


class Solution:
    def maxSum(self, nums: List[int], m: int, k: int) -> int:
        maxSum, sum = 0, 0
        cnt = defaultdict(int)
        uniqueCount = 0
        left, right = 0, 0

        while right < len(nums):
            if right - left == k:
                cnt[nums[left]] -= 1
                if cnt[nums[left]] == 0:
                    uniqueCount -= 1
                sum -= nums[left]
                left += 1

            if cnt[nums[right]] == 0:
                uniqueCount += 1
            cnt[nums[right]] += 1
            sum += nums[right]

            right += 1

            if right - left == k and uniqueCount >= m:
                maxSum = max(maxSum, sum)

        return maxSum