LeetCode 2762. Continuous Subarrays(JAVA)

출처 : https://leetcode.com/problems/continuous-subarrays/description/?envType=daily-question&envId=2024-12-14

 

#문제

You are given a 0-indexed integer array nums. A subarray of nums is called continuous if:
Let i, i + 1, ..., j be the indices in the subarray. Then, for each pair of indices i <= i1, i2 <= j, 0 <= |nums[i1] - nums[i2]| <= 2.
Return the total number of continuous subarrays.
A subarray is a contiguous non-empty sequence of elements within an array.


0-인덱스 기반 정수 배열 nums가 주어집니다. nums의 부분 배열은 다음 조건을 만족할 때 **연속적(continuous)**이라고 합니다:
부분 배열의 인덱스를 i, i + 1, ..., j라고 할 때, 인덱스 쌍 i <= i1, i2 <= j에 대해 항상 0 <= |nums[i1] - nums[i2]| <= 2를 만족합니다.
연속적인 부분 배열의 총 개수를 반환하세요.
부분 배열은 배열 내에서 연속적인 비어 있지 않은 요소들의 시퀀스를 의미합니다.

접근 : Two Pointer 방식

nums가 아래와 같다고하자

nums

6

5

6

7

5

6

4

5

6

 

nums의 원소를 탐색하면서 최댓값과 최솟값을 갱신해나가면서 둘의 차이가 2를 초과하지않는 범위를 구하면

	0	1	2	3	4	5	6	7	8
nums	6	5	6	7	5	6	4	5	6
max	6	6	6	7	7	7	7
min	6	5	5	5	5	5	4
max - min	0	1	1	2	2	2	3

nums[0] ~ nums[5]의 범위가 나온다. 길이가 n인 부분수열의 수는 n(n+1)/2 이므로 

 

nums[0:5] 의 부분수열은 6 * 7 / 2 = 21개가 된다.

 

이어서 nums[6:8] 의 부분수열을 구하면되는가? 아니다

7을 만나기 직전까지 좌측으로 탐색을 진행하고 우측으로 탐색을 진행해야한다.

	0	1	2	3	4	5	6	7	8
nums	6	5	6	7	5	6	4	5	6
max				7	6	6	4	6	6
min				4	4	4	4	4	4
max - min				3	2	2	3	2	2

즉 nums[6:8] 가 아닌 nums[4:8]의 부분 수열을 구해야한다.

 

여기서 주의해야할것은 중복된 범위를 처리해주어야한다. 현재예시로는 nums[0:5] 와 nums[4:8]의 중복범위인 nums[4:5]중복을 처리해주어야한다.

 

때문에 문제에서 요구하는 답을 구하기위해서는 (nums[0:5]의 부분수열) + (nums[4:8]의 부분 수열) - (nums[4:5] 의 부분 수열 ) 을 해주어야한다.

 

전체코드

class Solution {
    public long continuousSubarrays(int[] nums) {
        int left = 0,right = 0;
        long cnt =0;
        int min = nums[0];
        int max = nums[0];
        for ( right =0; right < nums.length; right++) {
            min = Math.min(min, nums[right]);
            max = Math.max(max, nums[right]);
            if(max - min > 2){
            	//차이가 2를 초과한다면 현재까지 범위의 부분수열의 수를 더해준다
                long len = right - left;
                cnt += (len*(len+1))/2;
                left = right;
                
                //min,max를 초기화
                min = nums[right];
                max = nums[right];
                
                //이전의 최댓값을 만나기 직전까지 왼쪽으로 확장
                while(left > 0 && Math.abs(nums[right] - nums[left - 1]) <= 2){
                    left--;
                    max = Math.max(max, nums[left]);
                    min = Math.min(min, nums[left]);
                }
                
                //중복되는 범위 차감
                if (left < right) {
                    len = right - left;
                    cnt -= (len * (len + 1)) / 2;
                }
            }
        }
        long len = right - left;
        cnt += (len*(len+1))/2;
        
        return cnt;
    }
}