1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target (Java, Prefix Sum, Leetcode)

더해서 target이 만들어지는 부분배열을 구하고 겹치지 않는 부분배열의 최대 개수를 구하는 문제이다.

해당 문제는 Prefix Sum을 통해 문제를 해결할 수 있다.

 

 

Prefix Sum

prefix sum은 Memoization 기법을 이용한 풀이 방법으로 브루트 포스 풀이시 O(n^2) 이상의 시간 복잡도를 O(n)으로 낮출 수 있다.

 

prefix sum의 과정은 아래와 같은 코드로 나타낼 수 있다.

 

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

//prefix sum
-1 = -1
-1 + 3 = 2
...
-1 + 3 + ... + 2 + -9 = 5
[-1,2,7,8,12,14,5]

 

위와 같은 memoization을 마친 상황에서 target = 6을 찾아야 한다고 가정해보자.

이때 sum - target으로 prefix sum이 존재하는지 확인하는데 8 - 2 = 6으로 3번째 인덱스에서 원하는 부분합을 찾을 수 있다.

 

sum - target은 (해당 인덱스까지의 부분 총합 - target)이라는 값을 가지는 부분 총합이 해당 인덱스 이전에 존재했었는지 확인하는 과정이다. 

 

이때 sum - target이 존재한다면 그 이전까지의 부분 총합을 제거해서 더 짧은 부분배열을 만들 수 있다.

 

 -1 + 3 + 5 + 1 - (-1 + 3) == 2

 

풀이

Set 이용

class Solution {
    public int maxNonOverlapping(int[] nums, int target) {
    	//부분 배열 개수 저장
        var count = 0;
        //memoization
        var sum = 0;
        //O(1)으로 부분 총합에 접근
        var set = new HashSet<Integer>();
        //가장 먼저 만들어지는 부분 총합은 0이므로 0을 추가.
        set.add(0);
        
        for (var num : nums) {
            sum += num;
            //부분 총합이 set에 이미 저장되었다면
            if (set.contains(sum - target)) {
                count++;
                set.clear();
                sum = 0;
            }
            set.add(sum);
        }
        return count;
    }
}

 

Map 이용

class Solution {
    public int maxNonOverlapping(int[] nums, int target) {
        var map = new HashMap<Integer, Integer>();
        map.put(0,0);
        
        var result = 0; var sum = 0;
        
        for (var num : nums) {
            //0부터 해당 인덱스까지의 총합 sum
            sum += num;
            //해당 인덱스까지의 총합 - target == 이전 어딘가까지의 부분총합
            //map에 부분총합이 저장되어 있으면
            if (map.containsKey(sum - target)) {
                //개수를 + 1해서 저장. 업데이트 될때마다 최대값 갱신.
                result = Math.max(result, map.get(sum - target) + 1);
            }
            //해당 인덱스까지 구한 부분총합의 개수를 저장.
            map.put(sum, result);
        }
        return result;
    }
}

 

레퍼런스

https://leetcode.com/problems/maximum-number-of-non-overlapping-subarrays-with-sum-equals-target/