欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

滑动窗口和查找表的使用

程序员文章站 2022-06-01 22:49:29
...

1.滑动窗口

1.1LeetCode209

给定一个含有 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组如果不存在符合条件的连续子数组,返回 0。

示例: 

输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。

暴利解法,我们会分别找出所有连续子数组的和,时间复杂度将达到O(n^3)

滑动窗口思路:

1.定义一个变量,保存区间的数据nums[i...j+1],减少大量的重复计算

滑动窗口和查找表的使用

2.找到一个区间值满足要求

滑动窗口和查找表的使用

3.然后缩小区间找到另一个区间的满足要求,依次滑动到最后区间,找到最优解

滑动窗口和查找表的使用

 设计代码如下

  public int minSubArrayLen(int s, int[] nums) {
        int res = Integer.MAX_VALUE;
        int l = 0;
        int r = -1;
        int sum = 0;
        while (l < nums.length){
            if (sum < s && r + 1 < nums.length){
                sum += nums[++r];
            }
            else{
                sum -= nums[l ++];
            }
            if(sum >= s)
                res = Math.min(res,r - l + 1);
        }
        if(res > nums.length)
            return 0;
        return res;
    }

2.查找表

滑动窗口和查找表的使用

在java语言中,查找表一般有tree表和hash表,hash表的查找复杂度是O(1)级别,而tree表的时间复杂度为O(logN)级别

虽然hash表的查找复杂度性能很强,但是他由于是根据每个元素的hash值来确定其存在位置,所以他没有顺序性可言

2.1LeetCode 001

给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

暴利解法:找出改数组所有两个元素的和,时间复杂度为O(N^2)级别

如果采用查找表,我们把该数组所有元素全部放在HashMap(key(值),value(index))里面,然后遍历整个数组通过查找target - nums[i]在查找表中是否存在,查找过程为O(1)级别所以整个时间复杂度为O(N)

代码设计如下:

 public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                if (target == nums[i] * 2) {
                    res[0] = map.get(nums[i]);
                    res[1] = i;
                    return res;
                }
            }
              map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i ++){
            if (map.containsKey(target - nums[i]) && target - nums[i] != nums[i]){
                res[0] = i;
                res[1] = map.get(target - nums[i]);
                return res;
            }
        }
        return res;
    }

3.查找表和滑动窗口的结合案例

3.1 LeetCode220

给定一个整数数组,判断数组中是否有两个不同的索引 i 和 j,使得 nums [i] 和 nums [j] 的差的绝对值最大为 t,并且 i 和 j 之间的差的绝对值最大为 ķ

示例 1:

输入: nums = [1,2,3,1], k = 3, t = 0
输出: true

示例 2:

输入: nums = [1,0,1,1], k = 1, t = 2
输出: true

示例 3:

输入: nums = [1,5,9,1,5,9], k = 2, t = 3
输出: false

暴利解法,找到所有的i,j(满足i != j 且 j - i <= k)时间复杂度O(KN)

优化方案:我们可以定义一个查找表保存满足条件的区间所有值

滑动窗口和查找表的使用

2.每次添加一个值判断是否该查找表中是否存在有一个值满足要求,当达到最大区间后,查找表左边缩小区间,从而遍历另一个元素来判断查找表中是否存在元素满足要求

滑动窗口和查找表的使用

代码设计如下

    public static boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return false;
        }
        int l = 0;
        int lt = 0;
        TreeSet<Long> set = new TreeSet<>();
        while (l < nums.length && lt < nums.length){
            if (set.ceiling((long)nums[lt] - (long)t) != null  && set.ceiling((long)nums[lt] - (long)t) <= (long) nums[lt] + (long) t){
                return true;
            }
            set.add((long) nums[lt ++]);
            if (lt - l > k){
                set.remove((long) nums[l++]);
            }
        }
        return false;
    }

LeetCode更多解答:https://github.com/OMGye/LeetCode