[LeetCode] 697. Degree of an Array

轉自LeetCode

Given a non-empty array of non-negative integers nums, the degree of this array is defined as the maximum frequency of any one of its elements.

Your task is to find the smallest possible length of a (contiguous) subarray of nums, that has the same degree as nums.

Example 1:

Input: [1, 2, 2, 3, 1]
Output: 2
Explanation: 
The input array has a degree of 2 because both elements 1 and 2 appear twice.
Of the subarrays that have the same degree:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
The shortest length is 2. So return 2.

Example 2:

Input: [1,2,2,3,1,4,2]
Output: 6

Note:

nums.length will be between 1 and 50,000.

nums[i] will be an integer between 0 and 49,999.

<Solution>

想法如下

• 所有符合條件的subarray，都至少必須包含出現最多次的數字。因此，去紀錄每個數字的 leftmost index 和 rightmost index，以及出現的次數。當某個數字符合條件，最短長度就會是 rightmost index - leftmost index + 1

• 因為可能有多個數字的都符合條件，所以必須在其中找到最短的

code 如下

Java(參考解答)

Kotlin