You are given an integer array nums.
An integer x is called special if:
x appears at least three times in nums.x are equally spaced in nums. In other words, if all occurrences of x are at indices i1 < i2 < ... < im, then i2 - i1 = i3 - i2 = ... = im - im-1.Return the number of distinct special integers in nums.
Example 1:
Input: nums = [1,8,1,5,1,5,8,5]
Output: 2
Explanation:
Therefore, the answer is 2.
Example 2:
Input: nums = [8,8,8,8]
Output: 1
Explanation:
8 is special because it occurs at equally spaced indices 0, 1, 2, and 3. Therefore, the answer is 1.
Example 3:
Input: nums = [8,6,6,8,8]
Output: 0
Explanation:
8 occurs at indices 0, 3, and 4, which are not equally spaced. 6 occurs only twice. Therefore, no integer is special.
Constraints:
3 <= nums.length <= 1051 <= nums[i] <= 109class Solution {
public int countSpecialIntegers(int[] nums) {
Map<Integer, Integer> freq = new HashMap<>();
Map<Integer, Integer> last = new HashMap<>();
Map<Integer, Integer> spacing = new HashMap<>();
Set<Integer> impossible = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
int F = freq.getOrDefault(nums[i], 0);
if (F >= 2 && spacing.get(nums[i]) != i - last.get(nums[i]))
impossible.add(nums[i]);
freq.put(nums[i], ++F);
if (F == 2)
spacing.put(nums[i], i - last.get(nums[i]));
last.put(nums[i], i);
}
int ans = 0;
for (Map.Entry<Integer, Integer> e : freq.entrySet())
if (e.getValue() >= 3 && !impossible.contains(e.getKey()))
ans++;
return ans;
}
}