Java算法OJ（11）双指针练习

---

目录

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。我们按顺序处理每个元素，检查是否存在符合条件的元素对。

1. 对于 nums[0] = 1，set 为空，直接将 1 添加到 set。
2. 对于 nums[1] = 5，我们查找 set 中是否存在元素 >= 5 - 3 = 2，并且该元素应小于等于 5 + 3 = 8。在 set 中没有满足条件的元素，所以将 5 添加到 set。
3. 对于 nums[2] = 9，我们查找 set 中是否存在元素 >= 9 - 3 = 6，并且该元素应小于等于 9 + 3 = 12。找到 5，它满足条件，所以返回 true。

因此，这个例子会返回 true，因为存在元素对 (5, 9)，它们的差值为 4，满足 k=2 和 t=3。

3.小结

今天的分享到这里就结束了，喜欢的小伙伴不要忘记点点赞点个关注，你的鼓励就是对我最大的支持，加油！