문제

풀이

1. 배열을 이어붙여 원형배열을 구현
   ex) [7,9,1,1,4] -> [7,9,1,1,4,7,9,1,1]
2. 누적합을 구해준다.
3. 부분 수열 크기 1~n 까지의 부분합들을 Set에 넣어준다.

코드

import java.util.*;
class Solution {
    public int solution(int[] elements) {
        int answer = 0;
        int n=elements.length;
        int[] nums=new int[2*n-1];
        for(int i=0;i<n;i++)nums[i]=elements[i];
        for(int i=0;i<n-1;i++)nums[i+n]=elements[i];
        
        HashSet<Integer> set=new HashSet<>();
        int[] dp=new int[2*n-1];
        dp[0]=elements[0];
        for(int i=1;i<2*n-1;i++)dp[i]=dp[i-1]+nums[i];
        for(int i=1;i<=n;i++){
            for(int j=0;j<n;j++){
                int sum=0;
                if(j!=0)sum=dp[j+i-1]-dp[j-1];
                else sum=dp[j+i-1];
                set.add(sum);
            }
        }
        return set.size();
    }
}

#부분합 #누적합