[Sliding Window] Minimum Size Subarray Sum

 

Two-pointer technique에 있는 문제인데, sliding window라는 방법론으로 풀 수 있다고 하여 다뤄보고자 한다.

 

CNN 필터가 슥슥 지나가는 것처럼 window의 길이를 다루고, 이를 한 칸씩 옆으로 옮겨보는 방법으로 subarray들을 체크할 수 있다.

 

i와 j를 같이 돌릴건데, ij 같이 있다가 i, j / i,,j / i,,,j / i,,,,,j 이런 식으로 j를 늘려가면서 체크하고,

nums[i]를 빼주고 i 인덱스를 증가시켜준다. 코드를 주석과 함께 보자.

 

 

 

시간복잡도가 while이 2개 들어가서 별 고민없이 O(n^2)인 줄 알았으나, subarray 체크하는 부분에서 늘어나는거만큼 우리가 왼쪽의 i에서도 줄여주기 때문에, O(n)이라고 한다.

공간복잡도는 scalar variable들만 사용하니까 O(1)이다.