好的,根据你提供的代码和LeetCode题号(697),我将帮助你生成一个结构化的Markdown文档。首先,我们需要补充一些必要的信息,如题目描述、示例、思路分析等。如果你能提供这些信息会更好,否则我会基于常见的题解模式进行推测。
以下是完整的Markdown文档:
# LeetCode 697## 目录
- [题目描述](#题目描述)
- [示例](#示例)
- [思路分析](#思路分析)
- [代码段](#代码段)
- [代码逐行讲解](#代码逐行讲解)
- [复杂度分析](#复杂度分析)
- [总结的知识点](#总结的知识点)
- [整合](#整合)
- [总结](#总结)---## 题目描述给定一个非空且只包含非负数的整数数组 `nums`,数组的度定义为元素出现次数的最大值。找到与原数组具有相同度的最短连续子数组,并返回其长度。---## 示例### 示例 1**输入:**
```java
nums = [1, 2, 2, 3, 1]
输出:
2
解释:
- 数组的度是2,因为元素2出现了两次。
- 最短的子数组是从索引1到2,长度为2。
示例 2
输入:
nums = [1,2,2,3,1,4,2]
输出:
6
解释:
- 数组的度是3,因为元素2出现了三次。
- 最短的子数组是从索引1到6,长度为6。
思路分析
问题核心
找到与原数组具有相同度的最短连续子数组,并返回其长度。
思路拆解
- 统计每个元素的出现次数:
- 使用哈希表记录每个元素的出现次数。
- 确定数组的度:
- 找出出现次数最多的元素的次数。
- 寻找最短子数组:
- 使用滑动窗口技术来找到满足条件的最短子数组。
代码段
class Solution {public int findShortestSubArray(int[] nums) {int l = 0, r = 0, len = nums.length, res = len + 1;Map<Integer, Integer> map = new HashMap<>();Map<Integer, Integer> map1 = new HashMap<>();int count = 0;for (int i : nums) {map1.put(i, map1.getOrDefault(i, 0) + 1);count = Math.max(count, map1.get(i));}while (r < len) {map.put(nums[r], map.getOrDefault(nums[r], 0) + 1);r++;while (map.get(nums[r - 1]) == count) {map.put(nums[l], map.get(nums[l]) - 1);res = Math.min(res, r - l);l++;}}return res;}
}
代码逐行讲解
-
初始化变量:
int l = 0, r = 0, len = nums.length, res = len + 1;
- 初始化左右指针
l
和r
,数组长度len
,以及结果res
。
- 初始化左右指针
-
统计每个元素的出现次数:
Map<Integer, Integer> map = new HashMap<>(); Map<Integer, Integer> map1 = new HashMap<>(); int count = 0;for (int i : nums) {map1.put(i, map1.getOrDefault(i, 0) + 1);count = Math.max(count, map1.get(i)); }
- 使用
map1
统计每个元素的出现次数,并找出最大出现次数count
。
- 使用
-
滑动窗口查找最短子数组:
while (r < len) {map.put(nums[r], map.getOrDefault(nums[r], 0) + 1);r++;while (map.get(nums[r - 1]) == count) {map.put(nums[l], map.get(nums[l]) - 1);res = Math.min(res, r - l);l++;} }
- 使用滑动窗口技术查找满足条件的最短子数组。
-
返回结果:
return res;
复杂度分析
时间复杂度
- 统计元素出现次数:O(n)
- 滑动窗口遍历:O(n)
- 总时间复杂度:O(n)
空间复杂度
- 使用了两个哈希表存储元素及其出现次数:O(n)
总结的知识点
- 哈希表的应用:
- 用于统计元素出现次数。
- 滑动窗口技术:
- 用于高效查找满足条件的最短子数组。
- 数组度的概念:
- 数组中元素出现次数的最大值。
整合
class Solution {public int findShortestSubArray(int[] nums) {int l = 0, r = 0, len = nums.length, res = len + 1;Map<Integer, Integer> map = new HashMap<>();Map<Integer, Integer> map1 = new HashMap<>();int count = 0;for (int i : nums) {map1.put(i, map1.getOrDefault(i, 0) + 1);count = Math.max(count, map1.get(i));}while (r < len) {map.put(nums[r], map.getOrDefault(nums[r], 0) + 1);r++;while (map.get(nums[r - 1]) == count) {map.put(nums[l], map.get(nums[l]) - 1);res = Math.min(res, r - l);l++;}}return res;}
}
总结
通过使用哈希表统计每个元素的出现次数,并结合滑动窗口技术,可以高效地找到与原数组具有相同度的最短连续子数组。