C++로 풀어보는 합이 k와 같은 가장 긴 부분 배열 찾기

문제 설명

nums라는 배열과 목표값 k가 주어졌을 때, 원소들의 합이 정확히 k가 되는 부분 배열(subarray) 중 가장 긴 길이를 구하는 문제입니다. 조건을 만족하는 부분 배열이 존재하지 않는다면 0을 반환해야 합니다.

예를 들어 입력이 nums = [1, -1, 5, -2, 3], k = 3이라면 출력은 4가 됩니다. 부분 배열 [1, -1, 5, -2]의 합이 정확히 3이면서 가장 길기 때문입니다.

접근 방법: 누적 합(Prefix Sum)과 해시 맵

모든 부분 배열을 일일이 확인하는 브루트 포스 방식은 O(n²)의 시간이 걸리지만, 누적 합(prefix sum)과 해시 맵을 활용하면 O(n) 시간에 해결할 수 있습니다.

핵심 아이디어는 다음과 같습니다. 인덱스 i까지의 누적 합을 temp라고 할 때, 이전에 등장한 어떤 인덱스 j까지의 누적 합이 temp - k였다면, (j+1)부터 i까지의 부분 배열의 합은 정확히 k가 됩니다. 따라서 각 누적 합이 처음 나타난 인덱스만 저장하면 가장 긴 길이를 구할 수 있습니다.

알고리즘 단계

• 결과를 저장할 변수 ret := 0으로 초기화합니다.

• 누적 합의 첫 등장 인덱스를 저장할 맵 m을 정의합니다.

• n := nums의 크기로 설정합니다.

• temp := 0으로 초기화하고, m[0] := -1로 설정합니다(인덱스 0부터 시작하는 부분 배열도 처리하기 위함입니다).

• i := 0부터 i < n까지 반복합니다:

  • temp := temp + nums[i]

  • (temp - k)가 m에 존재하면:

    • ret := max(ret, i - m[temp - k])

  • temp가 m에 아직 없다면:

    • m[temp] := i

• ret을 반환합니다.

C++ 구현 예제

아래 구현을 통해 더 자세히 이해해 보겠습니다:

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int maxSubArrayLen(vector<int>& nums, int k) {
        int ret = 0;
        unordered_map<int, int> m;
        int n = nums.size();
        int temp = 0;
        m[0] = -1;
        for(int i = 0; i < n; i++){
            temp += nums[i];
            if(m.count(temp - k)){
                ret = max(ret, i - m[temp - k]);
            }
            if(!m.count(temp)){
                m[temp] = i;
            }
        }
        return ret;
    }
};
main(){
    Solution ob;
    vector<int> v = {1,-1,5,-2,3};
    cout << (ob.maxSubArrayLen(v, 3));
}

입력

[1,-1,5,-2,3], 3

출력

4

복잡도 분석

• 시간 복잡도: O(n) — 배열을 한 번만 순회하며, 해시 맵의 삽입과 조회는 평균적으로 O(1)입니다.

• 공간 복잡도: O(n) — 최악의 경우 서로 다른 누적 합이 n개 저장될 수 있습니다.