[Java] LeetCode 2444. Count Subarrays With Fixed Bounds

[Java] LeetCode 2444. Count Subarrays With Fixed Bounds

 

문   제 : 

일차원 배열 nums가 주어진다.

정수 minK, maxK가 주어진다.

nums의 부분 배열 중 최소값이 minK이고, 최대값이 maxK인 부분배열의 개수를 구해라.

 

Constraint

{ 2 <= nums.length <= 10^5 }

{ 1 <= nums[i], minK, maxK <= 10^6 }

 

 

Example )

Input: nums = [1,3,5,2,7,5], minK = 1, maxK = 5
Output: 2
Explanation: 
The fixed-bound subarrays are [1,3,5] and [1,3,5,2].

//////////////////////////////////////////////////////////

Input: nums = [1,1,1,1], minK = 1, maxK = 1
Output: 10
Explanation: 
Every subarray of nums is a fixed-bound subarray. There are 10 possible subarrays.

 

---

접   근 : 

Two Pointer 로 접근했다.

---

해   결 : 

반복문으로 배열을 돌면서 minK, maxK의 값을 벗어난 값의 인덱스를 구한다. (j라고 하자)

maxK의 인덱스를 구한다. (prevMaxIndex)

minK의 인덱스를 구한다. (prevMinIndex)

범위안에 들면서 maxK나 minK의 값을 가지는 인덱스 중 작은 인덱스를 기준으로 j만큼 뺀 값을 카운팅해준다.

이 의미는 범위가 벗어나기 직전까지의 subArray의 개수를 세주는 것이다. 그래서 범위가 벗어나는 부분의 인덱스를 저장하고 있다가, 조건을 만족하는 subArray가 중간에서 나타나게 되면 그 만큼의 개수를 세줄 수 있는 것이다.

---

결   과  :

class Solution {
    public long countSubarrays(int[] nums, int minK, int maxK) {
        long cnt=0;
        int prevMinIndex = -1;
        int prevMaxIndex = -1;
        int j = -1;
        
        for(int i=0; i<nums.length; i++){
            if(minK > nums[i] || maxK < nums[i])
                j = i;

            if(maxK == nums[i])
                prevMaxIndex = i;
            
            if(minK == nums[i])
                prevMinIndex = i;

            cnt += Math.max(0, Math.min(prevMaxIndex, prevMinIndex) - j);
        }
        return cnt;
    }
}