[programmers][X] 연속 부분 수열 합의 개수

03 Jun 2023 in Algorithm on Algorithm

https://school.programmers.co.kr/learn/courses/30/lessons/131701

• 총 시간복잡도 = O(n) * O(n) = O(n²)
  1. 첫번째 O(n) : for(int i = 1 ; i <= len ; i++)
  2. 두번째 O(n) : cal(int[] elements, int idx) 내부 for문

총 1000*1000

import java.util.*;

class Solution {

    Set<Integer> s = new HashSet<>();
    int len = 0;

    public int solution(int[] elements) {
        len = elements.length;

        for(int i = 1 ; i <= len ; i++){
            cal(elements, i);
        }

        return s.size();
    }

    private void cal(int[] elements, int idx){
        int sum = 0;
        for(int i = 0 ; i < idx ; i++){
            sum += elements[i];
        }

        s.add(sum);

        int left = 0;
        for(int i = idx ; i < idx+len ; i++){
            int right = i;
            if(right >= len) right = right - len;
            sum = sum - elements[left++] + elements[right];
            s.add(sum);
        }
    }
}