leetcode 2537

Given an integer array nums and an integer k, return the number of good subarrays of nums.

A subarray arr is good if there are at least k pairs of indices (i, j) such that i < j and arr[i] == arr[j].

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,1,1,1,1], k = 10
Output: 1
Explanation: The only good subarray is the array nums itself.
Example 2:

Input: nums = [3,1,4,3,2,2,4], k = 2
Output: 4
Explanation: There are 4 different good subarrays:

• [3,1,4,3,2,2] that has 2 pairs.
• [3,1,4,3,2,2,4] that has 3 pairs.
• [1,4,3,2,2,4] that has 2 pairs.
• [4,3,2,2,4] that has 2 pairs.

Constraints:

1 <= nums.length <= 105
1 <= nums[i], k <= 109

---

문제

• 정수 배열의 부분 배열을 추출해서 유효한 조건의 개수 출력 프로그램을 구현해야 하는 문제
• 접근 방법이 떠오르지 않아 막연히 이중 loop를 형성 후 손이 가는대로 코딩
• 어떤걸 왜 선택해서 어떻게 푸는지에 대한 사고력과 감각이 부족

---

내 코드

// nums의 좋은 부분 배열 개수 반환
// 부분 배열 arr = 인덱스 쌍(i,j)이 k개. i < j. arr[i] == arr[j]
// 부분 배열 = 배열내 비어있지 않고 연속된 요소 시퀀스
class Solution {
    public long countGood(int[] nums, int k) {
        int n = nums.length;
        int pair = 2;
        int[][] arr = new int[pair][n];
        int counts = 0;
        // k쌍 이상의 부분 배열을 구한다.
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[0][n] = nums[i];
                arr[1][n] = nums[j];
                if (nums[i] < nums[j] && arr[i] == arr[j]) {
                    counts++;
                }
            }
        }
        return counts;
    }
}

• 일정으로 인해 타임아웃 10분으로 제한 후 답지를 통한 학습 시도

—

답안

접근

• 두 포인터 방식 사용 문제 해결
• 왼쪽 포인터 열겨.
• 왼쪽 하위 배열의 왼쪽 경계
• 초기값 0 오른쪽 포인터 사용
• 오른쪽 하위 배열 오른쪽 경계 -> 초기값 -1
• 현재 열거된 항목에 대해 왼쪽 -> 오른쪽 계속 이동
• nums[left..right] 좋은 배열
• 오른쪽 이동 중 동일한 요소 수 증가. cnt[right] -> cnt[right] 증가해야함
• 오른쪽 위 추론에 따라 이동이 완료. 좋은 하위 배열의 수가 왼쪽 경계는 n-right, n 배열의 길이. 숫자
• 이 값을 최종 답변에 추가
• 오른쪽 이동 과정 중 동일한 요소의 수를 점진적으로 계산할 수 있음. 해시 맵 사용 가능
• cnt각 하위 배열 각 요소. 해당 요소가 나타나는 횟수를 기록
• 동일한 요소의 수를 점진적 계산 가능. 해시맵 사용 가능
• cnt[] 각 하위 배열 각 요소. 해당 요소 나타나는 횟수를 기록
• cnt[] 오른쪽 위의 추론에 따라 이동이 완료되면 좋은 하위 배열의 수가 왼쪽. 왼쪽 경계는 n-오른쪽, n배열의 길이
• Nuts 값을 최종 답변에 추가
• 이후 현재 좌측 경계 left 열거되면 동일한 요소의 수는 감소함
• cnt[left]-1, cnt[left] 또한 줄여야 함
• 모든 왼쪽 경계를 열거한 후 최종 답 얻을 수 있음

Int n = nums.length;
Int same = 0, right = -1;
HashMap<Integer, Integer> cnt = new HashMap<>();

Long answer = 0;
For (int left = 0; left < n; ++left)
{
	while(same < k && right + 1 < n)
{
	++right;
Same += cnt.getOrDefault(nums[right], 0;
	cnt.put(nums[right],
cnt.getOrDefault(nums[right], 0) + 1);
}
	if(same >= k) {
	and += n - right;
}
	cnt.put(nums[left],
	cnt.get(nums[left]) - 1);
	same -= cnt.get(nums[left]);
}
	return and;
}
}

• 복잡성
• Nums 배열 길이 허용
• 시간복잡도 : O(n)
• 왼쪽과 오른쪽 포인터 각각 배열 한번씩 순회
• 공간복잡도 : O(n)
• 해쉬맵 cnt 는 공간복잡도 O(n) 요구

---

소감

• 다른 사람들은 이런 접근이 보면 영감이 막 떠오르나?
• 내가 기본 공부가 부족한건가 감각이 부족한건가..
• 자괴감 max지만 연민할 시간이 없어 다음 task로 넘어가는 하루