数组题用滑动窗口yyds

本文主要是介绍数组题用滑动窗口yyds，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

数组题之存在重复元素专题

我一直以为leetcode的数组题是给人签到用的，结果发现一般只有一个数组的题目，都是不让你用O(N^2)暴力过的，得优化到O(nlogn)或者最好O(n)。

存在重复元素

217. 存在重复元素

难度简单

给定一个整数数组，判断是否存在重复元素。

如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

示例 1:

输入: [1,2,3,1]
输出: true

示例 2:

输入: [1,2,3,4]
输出: false

示例 3:

输入: [1,1,1,3,3,4,3,2,4,2]
输出: true

想要特地用滑动窗口(i前面的用TreeSet保存，由于题目没有设置答案不能距离nums[i]多远，所以无需维护TreeSet的长度，也即滑动窗口的长度就是[0,i])：

class Solution {
    public boolean containsDuplicate(int[] nums) {
        //滑动窗口，借助TreeSet实现O（nlogn）
        int length = nums.length;
        TreeSet<Integer> ts = new TreeSet<>();
        for(int i = 0;i < length;i++){
            if(ts.contains(nums[i])){
                return true;
            }
            ts.add(nums[i]);
        }
        return false;
    }
}

是可以过的，O(nlogn)的复杂度。

但是想测试不用TreeSet的滑动窗口（[j,i]）：

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        int length = nums.length;
        if(length == 0){
            return false;
        }
        for(int i = 0;i < length;i++){
            for(int j = 0;j < i;j++){
                if(nums[i] == nums[j]){
                    return true;
                }
            }
        }
        return false;
    }
}

然后就熟悉的超限了。。。

考虑到这题只需要检查重复元素即可，那就排序后直接判断是否与前一个元素相等就行了：

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        int length = nums.length;
        if(length == 0){
            return false;
        }
        for(int i = 1;i < length;i++){
            if(nums[i] == nums[i-1]){
                return true;
            }   
        }
        return false;
    }
}

这样就是O(n)。

存在重复元素2

219. 存在重复元素 II

难度简单

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。

示例 1:

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

示例 2:

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

示例 3:

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

滑动窗口yyds

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        //滑动窗口
        int length = nums.length;
        HashMap<Integer,Integer> hm = new HashMap<>();//<值，下标>
        for(int i = 0;i < length;i++){
            if(hm.containsKey(nums[i]) && i - hm.get(nums[i]) <= k){
                return true;
            }
            hm.put(nums[i],i);				//起到记录和覆盖的两个作用
        }
        return false;
    }
}

窗口为：[0,i]。

（曾想过动态规划，但是建立不出状态转移方程，所以就没法做。）

存在重复元素3

220. 存在重复元素 III

难度中等

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。

如果存在则返回 true，不存在返回 false。

示例 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

提示：

0 <= nums.length <= 2 * 104
-231 <= nums[i] <= 231 - 1
0 <= k <= 104
0 <= t <= 231 - 1

一开始以为很简单，然后就被教育了。这题主要是卡你两个地方：1. nums[i]-nums[j]可能会很大，大到超出int范围（两个int数相加减一定要考虑溢出的问题），解决方法就是用Long或者BigInteger（后来发现BigInteger实在大题小做，而且BigInteger使用不方便）。2. nums的长度可能会很大，比如一个测试用例长这样：

[2433,3054,9952,6470,2509,8502,-8802,-5276,6559,-9555,-4765,6399,6543,2027,1723,-3032,-3319,-7726,-1425,-7431,-7492,4803,7952,-6603,-784,-8011,6161,-6955,5800,5834,-6310,1097,2327,-4007,8664,-9619,5922,518,9740,9976,4257,-7803,6023,4189,-5167,-4699,2441,5941,3663,625,5402,-3447,8888,9040,-4811,-7547,6822,1415,9372,-9262,4584,4149,-276,-4019,198,608,-4466,5383,7871,3149,-8358,9270,3565,-882,-9494,-6475,9833,-7744,-598,5299,5976,7361,-9444,3771,-5718,9051,3469,-4028,4216,5506,-8611,-9744,-8007,213,-3454,-2420,6283,-5616,-3508,-1329,4694,-7219,2056,9063,-9648,-7722,-755,-4422,-9878,-5104,3344,4585,-6871,7970,-2867,-9631,-579,-7948,-7035,-6526,-7549,-4731,-4163,-5796,-97,7385,-7460,-925,-7538,18,7781,-6875,9067,3350,668,5070,8965,9204,-6108,5337,9710,5218,-4764,1369,-180,157,-3261,-843,2881,-6371,570,3832,6948,-6861,-3604,7183,-5271,-4031,-611,-4958,5115,188,5433,3273,6251,6943,5446,-6114,-3257,-6265,-6810,-5000,-4493,-2496,-7071,-5923,4855,9865,-5402,-9373,1309,-8436,-6972,1117,79,-4448,-5354,5109,-9729,1057,9207,9074,-7036,-1878,2614,1559,-4723,-4969,-2667,2641,1401... 82793 more chars
//我还删减了好多。。。这个用例长度长达8万

 //我以为解决了大数溢出就行了。。。结果，压根不能for(for(length))这样遍历
 import java.math.BigInteger;
 class Solution {
     public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
         int length = nums.length;
             for(int i = 0;i < length;i++){
               for(int j = i+1;j < length;j++){//用例有一个十万长度数组过不去
                   System.out.println("0");
                   if(nums[i] < 10000000 && nums[j] < 10000000){
                       if(Math.abs(nums[i]-nums[j]) <= t && Math.abs(i-j) <= k){
                           System.out.println("1");
                           return true;
                       }
                   }
                   else {
                       System.out.println("2");
                       BigInteger res1 = new BigInteger(nums[i]+"");
                       BigInteger res2 = new BigInteger(nums[j]+"");
                       BigInteger rest = new BigInteger(t+"");
                       if(res1.subtract(res2).abs().compareTo(rest) <= 0 && Math.abs(i - j) <= k){//[-2147483648,2147483647]会计算爆栈变成负数，
                         // System.out.println("i="+i+" j="+j);
                         // System.out.println("res="+res1+"  Math.abs(nums[i] - nums[j])="+Math.abs(res1)+"  Math.abs(i - j)="+Math.abs(i - j));
                         return true;
                       }
                   }  
               }
             }
             return false;
         
     }
 }
 
 //后来看了滑动窗口解法后不甘心，又尝试了下暴力的滑动窗口，还是无法过巨长长度的数组的测试用例
 import java.math.BigInteger;
 class Solution {
     public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
         int length = nums.length;
             for(int i = 0;i < length;i++){
               for(int j = i-1;j >= 0 && j >= i-k;j--){//用例有一个十万长度数组过不去
                //    System.out.println("0");
                   if(nums[i] < 10000000 && nums[j] < 10000000){
                       if(Math.abs(nums[i]-nums[j]) <= t && Math.abs(i-j) <= k){
                        //    System.out.println("1");
                           return true;
                       }
                   }
                   else {
                    //    System.out.println("2");
                       BigInteger res1 = new BigInteger(nums[i]+"");
                       BigInteger res2 = new BigInteger(nums[j]+"");
                       BigInteger rest = new BigInteger(t+"");
                       if(res1.subtract(res2).abs().compareTo(rest) <= 0 && Math.abs(i - j) <= k){//[-2147483648,2147483647]会计算爆栈变成负数，
                         // System.out.println("i="+i+" j="+j);
                         // System.out.println("res="+res1+"  Math.abs(nums[i] - nums[j])="+Math.abs(res1)+"  Math.abs(i - j)="+Math.abs(i - j));
                         return true;
                       }
                   }  
               }
             }
             return false;
         
     }
 }

看了宫水三叶的题解才发现诸如数组比较判断的题，直接暴力搜索是不行的，一旦长度达到十万就会超限了，必须考虑O(nlogn)/O(n)的解法。比如滑动窗口+O(logn)查找复杂度的数据结构：

 class Solution {
     public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
         int length = nums.length;
         //题目的意思是在[i-k,i]范围内([i-k,i+k]太大，反正是遍历i所以只需要取前一段)，是否存在[nums[i]-t,nums[i]+t]的nums[j]。
         //TreeSet是有序集合，放进去了就自动排序。
         TreeSet<Long> ts =  new TreeSet<>();
         for(int i = 0;i < length;i++){
             Long res1 = ts.floor(nums[i]*1L);//小于等于nums[i]的最大值
             Long res2 = ts.ceiling(nums[i]*1L);//大于等于nums[i]的最小值
             if(res1 != null && nums[i] - res1 <= t){
                 return true;
             }
             if(res2 != null && res2 - nums[i] <= t){
                 return true;
             }
             ts.add(nums[i]*1L);
             if(i >= k){
                 ts.remove(nums[i-k]*1L);//由于i是从0开始遍历的，所以i-k前面的TreeSet全部不要，就不会出现abs(nums[i] - nums[j]) <= t但是abs(i - j) >= k的情况了。
             }
         }
         return false;
     }
 }

桶排序，有点烧脑，不是我能想到的：

class Solution {
    long size;
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int length = nums.length;
        Map<Long,Long> map = new HashMap<>();//桶排序，每个桶是该下标对应的+-t范围,比如u下标，那么map.get(u)要是不为null就说明[u-t,u+t]有元素，只要维护这个表的长度不超过t即可。
        size = t+1L;
        for(int i = 0;i < length;i++){
            long u = nums[i] * 1L;
            long index = getIndex(u);
            if(map.get(index) != null){
                return true;
            }
            //检查相邻的桶，表示-t和+t这个范围，这个是重点，为什么要检查相邻的桶存不存在呢？因为getIndex()这个方法里，num/size后，处于[num-size,num+size]的数/size，会落入[num/size-1]、[num/size]、[num/size+1]这三个桶内。为啥？计算一下就知道了：2/3=0，3/3=1，4/3=1，5/3=1,6/3=2,7/3=2,10/3=3，处于[4-3,4+3]也即[1,7]的数，比如6，一定在6/3=2的2或者1或者3这个桶内，所以只需要查找这三个桶就能判断是否存在[num-size,num+size]的数了，再维护数量不超过k，就可以实现题目的意思。
            long l = index-1,r = index+1;
            if(map.get(l) != null && u - map.get(l) <= t){
                return true;
            }
            if(map.get(r) != null && map.get(r) - u <= t){
                return true;
            }
            map.put(index,u);
            if(i >= k){
                map.remove(getIndex(nums[i-k]*1L));
            }
        }
        return false;
    }
    //由数值本身计算出桶排序的下标
    long getIndex(long num){
        return num >= 0 ? num/size : (num+1)/size-1;
    }
}

总结：

对于题目的大数，一般不需要用到BigInteger类，只需要用Long即能解决大部分int溢出问题。 int转long只需要*1L或者+1L。

数组的滑动窗口解法很实用，但是滑动窗口也不能暴力搜，需要借助数据结构TreeSet实现O(logn)查找。

桶排序太高深了暂时不看了，精华在于getIndex。

每天一个无用小知识（不用也不会看，用到了百度就行）

HashMap的使用

判断有无一个键：hashmap.containsKey(“xxx”);

判断有无一个值：hashmap.constainsValue(“xxx”);

根据特定Key获取Value：HashMap.get(Key);

不能通过值直接获取键。

哪个是键哪个是值？：new HashMap<键，值>();

BigInteger的常用方法看这篇

这篇关于数组题用滑动窗口yyds的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程