문제 링크

내 코드

• 숫자 범위 10만 $\rightarrow$ DAT.

• 중복된 숫자 관리 $\rightarrow$ unordered_set

• 25ms, 111.43MB

class Solution {
public:
    long long maximumSubarraySum(vector<int>& nums, int k) {
        vector<int> dat(100'100, 0);
        unordered_set<int> numSet; // 중복되는 숫자들
        long long answer{}, sum{};
        for(int i{};i<k;++i) {
            sum += nums[i];
            dat[nums[i]]++;
            if(dat[nums[i]] > 1) numSet.insert(nums[i]);
        }

        if(numSet.empty()) answer = max(answer, sum);

        for(int i = k, e = static_cast<int>(nums.size());i<e;++i) {
            sum += nums[i];
            dat[nums[i]]++;
            if(dat[nums[i]] > 1) numSet.insert(nums[i]);

            sum -= nums[i - k];
            dat[nums[i-k]]--;
            if(dat[nums[i-k]] == 1) numSet.erase(nums[i-k]);

            if(numSet.empty()) answer = max(answer, sum);
        }

        return answer;
    }
};

Solution

Approach: Sliding Window

• 92ms, 98.28MB
• Complexity
  • Let $N$ be the size of nums.
  • Time Complexity: $O(N)$
  • Space Complexity: $O(N)$

class Solution {
public:
    long long maximumSubarraySum(vector<int>& nums, int k) {
        long long ans = 0;
        long long currentSum = 0;
        int begin = 0;
        int end = 0;

        unordered_map<int, int> numToIndex;

        while (end < nums.size()) {
            int currNum = nums[end];
            int lastOccurrence =
                (numToIndex.count(currNum) ? numToIndex[currNum] : -1);

            // if current window already has number or if window is too big,
            // adjust window
            while (begin <= lastOccurrence || end - begin + 1 > k) {
                currentSum -= nums[begin];
                begin++;
            }
            numToIndex[currNum] = end;
            currentSum += nums[end];
            if (end - begin + 1 == k) {
                ans = max(ans, currentSum);
            }
            end++;
        }
        return ans;
    }
};