刷题日常(找到字符串中所有字母异位词,​ 和为 K 的子数组​,​ 滑动窗口最大值​,全排列)

找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

题目分析：

1.将p里面的字符先丢进一个hash1中，只需要在S字符里面找到多少个和他相同的hash2即可

2.使用R遍历整个字符S，L记录匹配成功的第一个位置，用于返回最终结果在ret数据中

3.使用滑动窗口 窗口大小只需要跟p的大小一样即可

4.进窗口  使用R去遍历这个字符，

5.出窗口  当出现窗口大小 >p的个数的时候 ，此时将L上的元素移除hash2 然后L++

6.更新结果 当窗口大小 = p的个数 并且 hash1和hash2相等的时候 记录此时的L加入最终结果

细节1：窗口大小能不能直接用hash2的size（）记录？

答案是不行 因为可能漏 ，会出现重复字符

里面有3个元素 ，而hash.size（）却为2 所有肯定会出错

细节2：当窗口大小大于 p的个数时候 ，能不能直接移除L上的位置

答案也是不行 因为会出现重复元素 比如上图中的 b 为 2个，只需要出掉一个b ，你却结果直接把b元素都在hash移除，肯定是错误的

class Solution { public List findAnagrams(String s, String p) { List ret = new ArrayList(); int m = p.length(), n = s.length(); HashMap hash1 = new HashMap(); for (int i = 0; i < m; i++) { char ch = p.charAt(i); hash1.put(ch, hash1.getOrDefault(ch, 0) + 1); } HashMap hash2 = new HashMap(); int left = 0; for (int right = 0; right  m) { char ch1 = s.charAt(left); int count = hash2.get(ch1) - 1; if (count == 0) {  hash2.remove(s.charAt(left)); } else {  hash2.put(ch1, count); } left++; } // 出窗口 更新结果 if (hash2.equals(hash1)) { ret.add(left); } } return ret; }}

 和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

使用前缀和思想+哈希表 寻找某个区间之和为K

dp就是前缀和数组，可以快速得到某一区间的和。

hash表第一个变量定义为前缀和，第二个变量定义为出现的次数

使用一个哈希表记录前缀和出现的数字，以及它的个数

只需要看哈希表是否有（当前数字的前缀和-K ）

如果有，返回它对应的个数，如果没有，进哈希表

细节处理：哈希表中开始前，应当把0这个数字放进去，此时为1次

防止第一个数就是我们要找到的K

class Solution { public int subarraySum(int[] nums, int k) { HashMap hash = new HashMap(); int n = nums.length, count = 0; int preSum = 0; hash.put(0, 1); for (int i = 0; i < n; i++) { preSum += nums[i]; if (hash.containsKey(preSum - k)) { count += hash.getOrDefault(preSum - k, 0); } hash.put(preSum, hash.getOrDefault(preSum, 0) + 1); } return count; }}

 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

• 遍历给定数组中的元素，如果队列不为空且当前考察元素大于等于队尾元素，则将队尾元素移除。直到，队列为空或当前考察元素小于新的队尾元素；
• 当队首元素的下标小于滑动窗口左侧边界left时，表示队首元素已经不再滑动窗口内，因此将其从队首移除。
• 由于数组下标从0开始，因此当窗口右边界right+1大于等于窗口大小k时，意味着窗口形成。此时，队首元素就是该窗口内的最大值。

class Solution { public int[] maxSlidingWindow(int[] nums, int k) { Deque deque = new LinkedList(); int[] ret = new int[nums.length - k + 1]; int left = 0; for(int right = 0 ;right < nums.length; right++) { //判断队列不为空的情况下是否队列的尾巴元素要小于加入的元素 //小于的话 得不断弹出 while(!deque.isEmpty() && nums[deque.peekLast()] < nums[right]) { deque.pollLast(); } //添加下标元素，为了更好的比较left deque.addLast(right); if(deque.peekFirst() = k) { ret[left++] = nums[deque.peekFirst()]; } } return ret; }}

全排列

 题目分析：

 在有重复元素中的数组中，需要考虑如何剪枝，才能使最终的结果不出现相同的结果

如图中，

1.一个数字只能使用一次在整个过程，当进入下一层中，使用一个记录boolean数组记录上一层使用的状态，如果为true，意味着我们已经使用过此元素，那么我们就跳过这个索引，避免重复使用同一个元素。

2.本题难点，当在同一层中，如何剪枝？

例如第一个数字有4中选法，可以选择1 1 1 2，那么将肯定 3个1里面只能选择一次，不然必将会出现重复，所有此时得将后面出现的俩次1不选，才可以得出没有重复的结果

这个很简单，多加一次判断呗，当nums[i]跟nums[i-1]的位置进行比较 看看是否相同

为了避免乱序，我们开始前就得将数组进行排序，这样数组将是一个有序状态，才能比较

只考虑不合法的情况 当遇见不合法的情况下，直接continue，跳过此次循环

class Solution { List<List> ret; List path; boolean[] check; public List<List> permuteUnique(int[] nums) { check = new boolean[nums.length]; path = new ArrayList(); ret = new ArrayList(); Arrays.sort(nums); dfs(nums); return ret; } public void dfs(int[] nums) { if (path.size() == nums.length) { ret.add(new ArrayList(path)); return; } for (int i = 0; i < nums.length; i++) { // 设置不合法区别 if (check[i] == true || (i != 0 && nums[i - 1] == nums[i] && check[i - 1] == false)) { continue; } path.add(nums[i]); check[i] = true; dfs(nums); path.remove(path.size() - 1); check[i] = false; } }}

1. check[i] == true 条件

首先，check[i] == true 的条件是用来检查当前索引 i 是否已经被使用过。如果 check[i] 为 true，意味着 nums[i] 已经在当前排列路径 path 中被使用过了，那么我们就跳过这个索引，避免重复使用同一个元素。

2. (i != 0 && nums[i - 1] == nums[i] && check[i - 1] == false) 条件

这个条件是避免重复排列产生的关键。为了理解这个条件，我们需要知道它的作用：

• nums[i - 1] == nums[i]：这个条件判断当前元素 nums[i] 是否和前一个元素 nums[i - 1] 相等。如果相等，说明这两个元素是相同的。

• check[i - 1] == false：这个条件确保前一个元素 nums[i - 1] 在当前排列路径中没有被使用过。也就是说，只有当前一个元素还没有被使用时，才允许使用当前的重复元素。

只考虑合法的情况 

class Solution { List<List> ret; List path; boolean[] check; public List<List> permuteUnique(int[] nums) { check = new boolean[nums.length]; path = new ArrayList(); ret = new ArrayList(); Arrays.sort(nums); dfs(nums); return ret; } public void dfs(int[] nums) { if (path.size() == nums.length) { ret.add(new ArrayList(path)); return; } for (int i = 0; i < nums.length; i++) { // 合法区间 if (check[i] == false && (i == 0 || nums[i] != nums[i - 1] || check[i - 1] == true)) { path.add(nums[i]); check[i] = true; dfs(nums); path.remove(path.size() - 1); check[i] = false; } } }}