[Arrrays and String] 713. Subarray Product Less Than K (투포인트와 슬라이딩 윈도우 개념 헷갈림)

https://leetcode.com/problems/subarray-product-less-than-k/

Subarray Product Less Than K - LeetCode

• 코드 템플릿 :  3. Sliding window( can be two points) => 

 

int fn(vector<int>& arr) {
    int left = 0, ans = 0, curr = 0; 

    for (int right = 0; right < arr.size(); right++) { // right 가 0부터시작하는것이 핵심
        // do logic here to add arr[right] to curr

        while (WINDOW_CONDITION_BROKEN) {
            // remove arr[left] from curr
            left++;
        }

        // update ans
    }

    return ans;
}

• Time complexity: O(n)
• Space: O(1)
• 난이도: medium
• 숙지할것들:

1. 슬라이딩 윈도우 개념(다시 보니까 기억안나서 다시공부 :-): 으아아앜 릿코드 개념혼동되게하네! 

 

릿코드에서 지칭하는 sliding window는 window 의 크기가 dynamic size 혹은 fixed size가 될 수 있는데 통상적으로는 fixed size로 칭하는것. => dynamic window size가 들어간 알고리즘은 two point에 가까운 방식으로 치부하되 접근법이 right index가 어레이 끝에서부터 마이너스되며 시작하지않고 처음부터(0)부터 플러스 카운팅되며 검색을한다. 

참고 : https://bbangson.tistory.com/72

 

  템플릿 이름이 sliding window인 이유인것은  2개의 two point 접근방식중 1번과 모양새가 같음

1) 2개의 포인터 변수 시작점이 배열의 시작점인 경우.  

2) 정렬된 배열 안에서 2개의 포인터 변수가 각각 시작점과 끝점(arr.length-1)에 위치한 경우  

 

다시 정리하면 

two points 
1) 2개의 포인터 변수 시작점이 배열의 시작점인 경우 및 윈도우 사이즈 가변 
2) 정렬된 배열 안에서 2개의 포인터 변수가 각각 시작점과 끝점(arr.length-1)에 위치한 경우  

sliding window
1) 2개의 포인터 변수 시작점이 배열의 시작점인 경우 및 윈도우 사이즈가 고정

2. while 루프는 O(1)의 시간을 가질 수 있어 전체 O(n)의 시간 복잡도를 가질수있음. O(1)의 시간은 amortized analysis  를 사용해서 분석했을때.( 최악만 고려하지않고 평균적인 시간을 고려한것이라함)

---

713. Subarray Product Less Than K  정답지

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if (k <= 1) {
            return 0;
        }

        int ans = 0, left = 0, curr = 1;
        for (int right = 0; right < nums.size(); right++) {
            curr *= nums[right];
            while (curr >= k) {
                curr /= nums[left];
                left++;
            }
            
            ans += right - left + 1;
        }
        
        return ans;
    }
};

 

어휴 힘들다