用滑动数组判断某个范围内是否有重复元素
给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。
public boolean containsNearbyDuplicate(int[] nums, int k) { Set<Integer> set = new HashSet<Integer>(); int length = nums.length; for (int i = 0; i < length; i++) { if (i > k) { set.remove(nums[i - k - 1]); } if (!set.add(nums[i])) { return true; } } return false; } //hash暴力 public boolean containsNearbyDuplicate(int[] nums, int k) { Map<Integer, Integer> map = new HashMap<Integer, Integer>(); int length = nums.length; for (int i = 0; i < length; i++) { int num = nums[i]; if (map.containsKey(num) && i - map.get(num) <= k) { return true; } map.put(num, i); } return false; }
子数组中的最大平均数
给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。
请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。
输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
对于这道题，最基本的想法就是，先取得一开始的最基本的k个数据，然后组成和。
然后每一次都向后继续遍历数据，由于我们的窗口大小为k是固定的，因此我们需要删除最早的数据，然后放入当前数据，来保证数据和的个数依旧为k个。
所以我们可以得到 sum = sum - nums[i-k] + nums[i]
之后，我们在不断的遍历过程中，就能得到最大的平均值了。
public double findMaxAverage(int[] nums, int k) { int sum = 0; for(int i=0;i<k;i++){ sum+=nums[i]; } int sumMax = sum; for(int i=k;i<nums.length;i++){ sum = sum - nums[i-k] + nums[i]; sumMax = Math.max(sum,sumMax); } return sumMax * 1.0 /k; }
滑动窗口得到最大利润
给定一个数组arr，它的第 i 个元素 arr[i] 表示一个商品当天的价格。
你需要选择一个日子买入这个商品，然后在之后的日子卖出，那么在那一天卖出你能得到最大的利润？
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[12,1,3,3,6,5]
输出：5
解释：在1的时候买入，在6的时候卖出
public int maxProfit(int[] arr) { int min = Integer.MAX_VALUE; int earn = 0; for(int i=0;i<arr.length;i++){ min=Math.min(arr[i],min); earn = Math.max(earn,arr[i]-min); } return earn; }
字符串的最长无重复子串
这道题要求得到一个不重复的最长字符串子串，那么我们如果要保证得到的数据不重复，可以考虑使用Set，我们使用set集合的add方法的时候，如果元素已经存在，那么add会失败，借此我们可以判断是否遇到了重复字符。
因此我们可以很快的写出O（N2)的暴力遍历的方法，外层循环用于控制每一个字符的开始位置。
内层循环控制当前字符串什么时候遇到重复字符，并且记录这一个过程中遇到的最长的字符串的长度。
而这个过程中，我们发现，其实我们并没有保留之前上一次遍历给我们留下的子串，而是直接完全重新开始。
那么，如果使用滑动窗口的思想，
就知道，abca中，遇到最后一个a的时候，出现重复了，但是我们可以确定的是，bc是一定不重复的，这个是我们可以保留的，那么我们就以bc为先决条件，继续向后遍历，然后判断下一个字符是否重复，不重复继续添加到set中，然后重复这个过程。
//暴力解法 public int lengthOfLongestSubstring(String s) { Set<Character> set = new HashSet<>(); int n = s.length(); int max = 0; for (int i = 0; i < n; i++) { int index = i; int cur = 0; while (index < n && set.add(s.charAt(index++))) { cur++; max = Math.max(cur, max); } set.clear(); } return max; } //滑动窗口解法 public int lengthOfLongestSubstring(String s) { Set<Character> set = new HashSet<>(); int n = s.length(); int max = 0; int index = 0; //内部的遍历的index索引，用于记录上一次遍历到的数据的位置 for (int i = 0; i < n; i++) {//i是最开头元素的索引位置 if (set.size()>=1) { //只有set里面有元素的时候才可以移除开头 set.remove(s.charAt(i - 1)); } while (index < n && !set.contains(s.charAt(index))) { set.add(s.charAt(index)); index++; } //index-i就可以得到当前这次出现重复的元素的位置与起始字符所在位置的差了 要是不能理解的可以debug //这里注意 index 是需要保留的 而不是每一次都从index=i开始 //不然 你上一次遍历的字符串给你留下的资产就没用了 max = Math.max(max, index - i); } return max; }
