上海网站 备案品牌运营管理有限公司
目录
1.前言
2.正文
2.1存在重复数字
2.1.1题目
2.1.2解法一代码
解析：
2.1.3解法二代码
解析：
2.2存在重复数字plus
2.2.1题目
2.2.2代码
2.2.3解析
3.小结
1.前言
哈喽大家好吖，今天来给大家分享双指针算法的相关练习，题目不多，但却是很经典的双指针的模型，废话不多说让我们开始吧。
2.正文
2.1存在重复数字
2.1.1题目
219. 存在重复元素 II - 力扣（LeetCode）
https://leetcode.cn/problems/contains-duplicate-ii/?envType=problem-list-v2&envId=sliding-window
2.1.2解法一代码
class Solution {public boolean containsNearbyDuplicate(int[] nums, int k) {// 创建一个 HashMap，用于存储每个元素的最后出现索引HashMap<Integer, Integer> map = new HashMap<>();// 遍历数组中的每个元素for (int i = 0; i < nums.length; i++) {// 检查当前元素是否已经出现在 map 中，并且索引差是否小于等于 kif (map.containsKey(nums[i]) && (i - map.get(nums[i]) <= k)) {return true; // 如果条件满足，返回 true}// 将当前元素及其索引存入 map 中map.put(nums[i], i);}// 如果遍历完所有元素都没有找到满足条件的对，返回 falsereturn false;}
}
解析：
核心思路：
哈希表存储元素的索引：
map用来存储数组中每个元素的最新出现的索引。map.put(nums[i], i)会在每次遍历时更新该元素的索引。- 通过
map.containsKey(nums[i])检查当前元素是否已经在哈希表中出现过，如果出现过，则进一步判断当前索引与该元素上次出现的索引之差是否小于等于k。判断条件：
- 如果当前元素已经在哈希表中，并且当前索引
i与该元素最后一次出现的索引之间的差值i - map.get(nums[i])小于等于k，则说明找到了符合条件的重复元素对，直接返回true。- 如果条件不满足，则将当前元素及其索引存入
map中，继续遍历下一个元素。返回值：
- 如果遍历完所有元素都没有找到满足条件的元素对，则返回
false。
2.1.3解法二代码
class Solution {public boolean containsNearbyDuplicate(int[] nums, int k){// 使用 HashSet 存储当前窗口内的元素HashSet<Integer> set = new HashSet<>();// 遍历数组中的每个元素for(int i = 0; i < nums.length; i++){// 保证滑动窗口的大小不超过 kif(i > k) set.remove(nums[i - k - 1]);// 如果当前元素已经存在于 set 中，说明找到了重复的元素，返回 trueif(!set.add(nums[i])) return true;}// 如果没有找到符合条件的重复元素，返回 falsereturn false;}
}
解析：
思路核心：
HashSet存储当前滑动窗口中的元素：
set是用来存储当前窗口中的元素。如果set中已经存在当前元素，则说明找到了一个重复元素，并且这个元素满足索引差不超过k，因此返回true。滑动窗口的维护：
- 使用
if (i > k)来控制滑动窗口的大小，确保窗口中最多包含k个元素。当索引i大于k时，意味着滑动窗口的左边界已经移动，需要移除set中索引i - k - 1位置的元素，即set.remove(nums[i - k - 1])。这样保证了窗口大小不会超过k。判断重复元素：
set.add(nums[i])如果当前元素已经在set中存在，add方法会返回false，表示没有成功添加新元素，此时就说明找到了重复元素，返回true。- 如果
set.add(nums[i])返回true，则说明当前元素不重复，继续遍历下一个元素。返回
false：
- 如果遍历完所有元素后都没有找到重复元素，则返回
false。
2.2存在重复数字plus
2.2.1题目
220. 存在重复元素 III - 力扣（LeetCode）https://leetcode.cn/problems/contains-duplicate-iii/description/?envType=problem-list-v2&envId=sliding-window
2.2.2代码
class Solution {public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {int n = nums.length;// 创建一个 TreeSet 来存储滑动窗口中的元素TreeSet<Long> set = new TreeSet<Long>();// 遍历 nums 数组中的每个元素for (int i = 0; i < n; i++) {// 检查滑动窗口中是否存在满足条件的元素Long ceiling = set.ceiling((long) nums[i] - (long) t);// 如果找到一个元素满足条件，返回 trueif (ceiling != null && ceiling <= (long) nums[i] + (long) t) {return true;}// 将当前元素添加到 TreeSet 中set.add((long) nums[i]);// 保持滑动窗口的大小为 k，如果当前索引 i 大于或等于 k// 则移除窗口中最左边的元素if (i >= k) {set.remove((long) nums[i - k]);}}// 如果遍历完所有元素后都没有找到满足条件的元素对，返回 falsereturn false;}
}
2.2.3解析
核心思路：
TreeSet 用于查找邻近元素：
TreeSet是一个有序集合，它根据元素的大小自动排列，因此可以快速查找给定范围内的元素。这里，我们使用ceiling方法来查找大于等于nums[i] - t的最小元素，如果这个元素与当前nums[i]的差小于等于t，则满足题目条件，返回true。滑动窗口： 我们维护一个大小为
k的滑动窗口。每次遍历一个新元素时，先在TreeSet中查找该元素的邻近值（是否满足条件），然后将当前元素添加到窗口中。为了保持窗口大小为k，如果当前索引大于等于k，则移除窗口中最左边的元素。这样，滑动窗口始终保持最新的k个元素。
让我们来模拟一下，假设我们有以下数组：
nums = [1, 5, 9, 1, 5, 9], k = 2, t = 3
在这个例子中，滑动窗口的大小是 2（即最多允许相隔 2 个元素），并且差值要求不超过 3。我们按顺序处理每个元素，检查是否存在符合条件的元素对。
- 对于
nums[0] = 1，set为空，直接将 1 添加到set。- 对于
nums[1] = 5，我们查找set中是否存在元素>= 5 - 3 = 2，并且该元素应小于等于5 + 3 = 8。在set中没有满足条件的元素，所以将 5 添加到set。- 对于
nums[2] = 9，我们查找set中是否存在元素>= 9 - 3 = 6，并且该元素应小于等于9 + 3 = 12。找到 5，它满足条件，所以返回true。因此，这个例子会返回
true，因为存在元素对(5, 9)，它们的差值为 4，满足k=2和t=3。
3.小结
今天的分享到这里就结束了，喜欢的小伙伴不要忘记点点赞点个关注，你的鼓励就是对我最大的支持，加油！