找到字符串中所有字母异位词
给定两个字符串 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<Integer> findAnagrams(String s, String p) {List<Integer> ret = new ArrayList<>();int m = p.length(), n = s.length();HashMap<Character, Integer> hash1 = new HashMap<>();for (int i = 0; i < m; i++) {char ch = p.charAt(i);hash1.put(ch, hash1.getOrDefault(ch, 0) + 1);}HashMap<Character, Integer> hash2 = new HashMap<>();int left = 0;for (int right = 0; right < n; right++) {char ch = s.charAt(right);// 进窗口hash2.put(ch, hash2.getOrDefault(ch, 0) + 1);// 判断while (right - left + 1 > 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<Integer, Integer> 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<Integer> 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();}//添加下标元素，为了更好的比较leftdeque.addLast(right);if(deque.peekFirst() < left) {deque.pollFirst();}//判断窗口是否成型 加入到最终结果if(right + 1 >= 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<Integer>> ret;List<Integer> path;boolean[] check;public List<List<Integer>> 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<Integer>> ret;List<Integer> path;boolean[] check;public List<List<Integer>> 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;}}}
}
