Java算法OJ(11)双指针练习

发布于:2024-11-29 ⋅ 阅读:(24) ⋅ 点赞:(0)


目录

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)icon-default.png?t=O83Ahttps://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 中,并且索引差是否小于等于 k
            if (map.containsKey(nums[i]) && (i - map.get(nums[i]) <= k)) {
                return true;  // 如果条件满足,返回 true
            }
            // 将当前元素及其索引存入 map 中
            map.put(nums[i], i);
        }
        
        // 如果遍历完所有元素都没有找到满足条件的对,返回 false
        return 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++){
            // 保证滑动窗口的大小不超过 k
            if(i > k) set.remove(nums[i - k - 1]);
            
            // 如果当前元素已经存在于 set 中,说明找到了重复的元素,返回 true
            if(!set.add(nums[i])) return true;
        }
        
        // 如果没有找到符合条件的重复元素,返回 false
        return 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)icon-default.png?t=O83Ahttps://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);
            
            // 如果找到一个元素满足条件,返回 true
            if (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]);
            }
        }
        
        // 如果遍历完所有元素后都没有找到满足条件的元素对,返回 false
        return 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] = 1set 为空,直接将 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=2t=3

3.小结

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


网站公告

今日签到

点亮在社区的每一天
去签到