wordpress 首页缩略图,保定seo网络推广,手机怎么做电子书下载网站,做装饰网站公司目录
1.前言
2.正文
2.1存在重复数字
2.1.1题目 2.1.2解法一代码
解析#xff1a;
2.1.3解法二代码
解析#xff1a;
2.2存在重复数字plus
2.2.1题目
2.2.2代码
2.2.3解析
3.小结 1.前言
哈喽大家好吖#xff0c;今天来给大家分享双指针算法的相关练习… 目录
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 - 力扣LeetCodehttps://leetcode.cn/problems/contains-duplicate-ii/?envTypeproblem-list-v2envIdsliding-window 2.1.2解法一代码
class Solution {public boolean containsNearbyDuplicate(int[] nums, int k) {// 创建一个 HashMap用于存储每个元素的最后出现索引HashMapInteger, 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 存储当前窗口内的元素HashSetInteger 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 - 力扣LeetCodehttps://leetcode.cn/problems/contains-duplicate-iii/description/?envTypeproblem-list-v2envIdsliding-window
2.2.2代码
class Solution {public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {int n nums.length;// 创建一个 TreeSet 来存储滑动窗口中的元素TreeSetLong set new TreeSetLong();// 遍历 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] 1set 为空直接将 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满足 k2 和 t3。 3.小结
今天的分享到这里就结束了喜欢的小伙伴不要忘记点点赞点个关注你的鼓励就是对我最大的支持加油
