优选算法 - 1 （ 双指针 移动窗口 8000 字详解 ）

一：双指针

1.1 移动零

题目链接：283.移动零

class Solution {public void moveZeroes(int[] nums) {for(int cur = 0, dest = -1 ; cur < nums.length ; cur++){if(nums[cur] == 0){}else{dest++; // dest 先向后移动⼀位int tmp = nums[cur];nums[cur] = nums[dest];nums[dest] = tmp;}}}
}

这类题目的本质就是数组划分，根据某个规则将数组分成若干个区间，在此题中，我们可以使用双指针算法划分数组的区间，用数组下标充当指针，两个指针会划分成3个区间

1.2 复写零

题目链接：复写零

class Solution {public void duplicateZeros(int[] arr) {int length = arr.length;int virtualLength = 0; // 虚拟长度，表示将所有 0 复写两次后的长度int lastIndex = 0; // 表示最后一个需要处理的索引// 第一步：确定最后一个需要处理的索引for (lastIndex = 0; lastIndex < length; lastIndex++) {virtualLength += (arr[lastIndex] == 0) ? 2 : 1; // 0 占两个位置，非 0 占一个位置if (virtualLength >= length) break; // 超过数组长度时停止}int dest = length - 1; // 目标位置，从数组最右端开始// 细节：如果最后一个复写数的索引的值刚好为 0，我们只需把 0 复制一次即可//因为如果正常来赋值的话，最后一个复写数的值为 0 时，我们只需把 0 复制一次即可，复制两次会造成越界，所以我们从右往左覆盖时也只需复制一次//virtualLength > length 保证了数组至少有一个 0 if (virtualLength > length && arr[lastIndex] == 0) {arr[dest--] = 0;lastIndex--; // 回退 lastIndex，继续处理前面的元素}// 第二步：从右向左复制元素while (lastIndex >= 0) {if (arr[lastIndex] == 0) {arr[dest--] = 0; // 复制第一个 0arr[dest--] = 0; // 复制第二个 0} else {arr[dest--] = arr[lastIndex]; // 复制非零元素}lastIndex--; // 移动到前一个元素}}
}

1.3 快乐数

题目链接：快乐数

class Solution {//封装一个求 n 每一位的平方和的函数public int bitsum(int n){int sum = 0;while(n > 0){int bit = n % 10;sum += bit * bit;n /= 10;}return sum;}public boolean isHappy(int n) {//先让快指针走一步int slow = n;int fast = bitsum(n);while(slow != fast){//慢指针走一步，快指针走两步slow = bitsum(slow);fast = bitsum(bitsum(fast));}      return fast == 1;}
}

1.4 盛水最多的容器

题目链接： 盛水最多的容器

class Solution {public int maxArea(int[] height) {// left 是左指针， right 是右指针，ret存储最大的体积结果int left = 0;int right = height.length - 1;int ret = 0;while(left < right){int v = Math.min(height[left], height[right]) * (right - left);ret = Math.max(ret,v);if(height[left] < height[right]) left++;else right --;}return ret;}
}

1.5 有效三角形的个数

题目链接：有效三角形的个数

class Solution {public int triangleNumber(int[] nums) {//首先先对数组排序，并用 ret 存储有效三角形的个数Arrays.sort(nums);int ret= 0;int n = nums.length - 1;//先固定一个最大的数,最大的数最小的下标应该是 2，因为元素是有 3 个的for(int i = n ; i >= 2 ; i --){int left = 0;int right = i - 1;while (left < right) {    //如果左指针加上右指针的值大于固定数的值if(nums[left] + nums[right] > nums[i]){ret += (right - left);right--;}else{left++;}}    }return ret;}
}

1.6 和为 s 的两个数字

题⽬链接：和为s的两个数字

class Solution
{public int[] twoSum(int[] nums, int target){int left = 0, right = nums.length - 1;while(left < right){int sum = nums[left] + nums[right];if(sum > target) right--;else if(sum < target) left++;else return new int[] {nums[left], nums[right]};}// 照顾编译器return new int[]{0};}
}

1.7 三数之和

题目链接：三数之和

import java.util.*;class Solution {public List<List<Integer>> threeSum(int[] nums) {// 先对数组进行排序Arrays.sort(nums);List<List<Integer>> ret = new ArrayList<>();int n = nums.length;// 固定一个数，从左往右固定，最少保留两个数for (int i = 0; i < n - 2; i++) {// 跳过固定数的重复情况if (i > 0 && nums[i] == nums[i - 1]) continue;int left = i + 1, right = n - 1, target = -nums[i];while (left < right) {int sum = nums[left] + nums[right];if (sum > target)  right--; else if (sum < target)  left++;else {// 找到符合条件的三元组ret.add(Arrays.asList(nums[i], nums[left], nums[right]));left++; right--;// 跳过重复的 left 和 right 元素，防止结果重复while (left < right && nums[left] == nums[left - 1]) left++;while (left < right && nums[right] == nums[right + 1]) right--;}}}return ret;}
}

1.8 四数之和

题目链接：四数之和

import java.util.*;class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {//先对数组进行排序Arrays.sort(nums);int n = nums.length;List<List<Integer>> ret = new ArrayList<>();//接着固定两个数for(int i = 0 ; i < n   ;){for(int j = i + 1 ; j < n ; ){int left = j + 1 , right = n - 1;long aim = (long)target - nums[i] - nums[j];while(left < right){int sum = nums[left] + nums[right];if(sum > aim) right--;else if(sum < aim) left++;else{ret.add(Arrays.asList(nums[i], nums[j], nums[left++],nums[right--]));//接着进行去重while(left < right && nums[left] == nums[left - 1]) left++;while(left < right && nums[right] == nums[right + 1]) right--;}}//循环执行完毕后，让第二个固定的数加 1j++;while(j < n && nums[j] == nums[j - 1]) j++;}i++;while(i < n && nums[i] == nums[i - 1]) i++;}return ret;}
}

二： 移动窗口

2.1 长度最小的子数组

题目链接：长度最小的子数组

class Solution {public int minSubArrayLen(int target, int[] nums) {// size 用于记录最小子数组的长度，sum 用于存储子数组的和int n = nums.length, sum = 0, size = Integer.MAX_VALUE;int left = 0, right = 0;while(right < n){//进窗口sum += nums[right];//出窗口while(sum >= target){size = Math.min(size,right - left + 1);sum -= nums[left++];} //一次迭代完成后让右指针继续走right++;}//判断一下 size 是否被更新过return size == Integer.MAX_VALUE ? 0 : size;}
}

2.2 无重复字符的最长子串

题目链接：无重复字符的最长子串

class Solution {public int lengthOfLongestSubstring(String ss) {// 将字符串转换为字符数组char[] s = ss.toCharArray();// 用数组来模拟哈希表，记录字符出现次数int[] charCount = new int[128];int left = 0, maxLen = 0;for (int right = 0; right < s.length; right++) {char rightChar = s[right];// 将当前字符加入窗口，并更新计数，字符会自动转换为对应的 ascii 值charCount[rightChar]++;// 当出现重复字符时，缩小窗口直到没有重复字符while (charCount[rightChar] > 1) {char leftChar = s[left];charCount[leftChar]--;  // 将左边的字符移出窗口left++;}// 更新最大无重复子串的长度maxLen = Math.max(maxLen, right - left + 1);}return maxLen;}
}

2.3 最大连续 1 的个数 III

题目链接：最大连续 1 的个数 III

class Solution {public int longestOnes(int[] nums, int k) {//定义左右指针和计数器 zero ，用于统计 0 的个数int left = 0, right = 0 ,zero = 0, n = nums.length, ret = 0;while(right < n){//进窗口if(nums[right] == 0) zero++;//出窗口while(zero > k){               if(nums[left++] == 0) zero--;}//每次循环都更新一下 ret ret = Math.max(ret,right - left + 1);right++;}return ret;}
}

2.4 将 x 减到 0 的最小操作数

题目链接：将 x 减到 0 的最小操作数

class Solution {public int minOperations(int[] nums, int x) {int sum = 0, left = 0, right = 0, n = nums.length;// 计算数组 nums 的总和for(int a : nums) sum += a;// 定义目标值 target（即我们希望找到一个子数组，使得它的和等于 sum - x）int target = sum - x;int total = 0; // 当前子数组的和int len = -1;  // 子数组的最大长度，初始为 -1 表示不存在// 如果 target 小于 0，表示 x 比数组总和还大，不可能得到，直接返回 -1if (target < 0) return -1;  // 使用滑动窗口在数组中寻找和为 target 的最长子数组while(right < n) {// 进窗口：将当前右边界的元素加入当前子数组的和total += nums[right];// 出窗口：当当前子数组的和大于 target 时，缩小窗口（从左边移出元素）while(total > target) total -= nums[left++];// 每次循环都要判断是否更新 len：当当前子数组的和等于 target 时，记录子数组的最大长度if(total == target) len = Math.max(len, right - left + 1);// 移动右边界，扩大窗口right++;}// 如果 len 仍为 -1，表示找不到符合条件的子数组，返回 -1// 否则，返回 n - len，表示需要移除的最小元素数目return (len == -1) ? -1 : n - len;}
}

2.5 水果成篮

题目链接：水果成篮

class Solution {public int totalFruit(int[] fruits) {//创建一个哈希表，用于存储水果的种类和数量Map<Integer, Integer> hash = new HashMap<>();int left = 0, right = 0, n = fruits.length, max = 0;while(right < n){//进窗口int ch1 = fruits[right];//通过 put 让 ch1 的值加一hash.put(ch1, hash.getOrDefault(ch1,0) + 1);//出窗口while(hash.size() > 2){int ch2 = fruits[left];//通过 put 让 ch2 的值减一hash.put(ch2, hash.get(ch2) - 1); //出窗口时，可能会让这个种类的数量变 0 ，此时要把这个种类踢出去if(hash.get(ch2) == 0) hash.remove(ch2);left++;}//每次循环都更新一下 max max = Math.max(max, right - left + 1);right++;}return max;}
}

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

题目链接：找到字符串中所有字母异位词

class Solution {public List<Integer> findAnagrams(String ss, String pp) {List<Integer> ret = new ArrayList<>();//不合理的情况，直接返回一个空的if(pp.length() > ss.length()) return ret;//接着把 ss 和 pp 转换为字符数组，并用 hash1 和 hash2 分别记录 s 和 p 中出现过的字符和次数，count 统计有效字符的个数char[] s = ss.toCharArray();char[] p = pp.toCharArray();int[] hash1 = new int[26];int[] hash2 = new int[26];for(int ch : p) hash2[ch - 'a']++;int left = 0, right = 0, count = 0, n = s.length;while(right < n){//进窗口 + 维护 countchar in = s[right];hash1[in - 'a']++;//进窗口后，如果 hash1 中的对应字符数量小于等于 hash2 中的数量，说明进入的是有效的字符if(hash1[in - 'a'] <= hash2[in - 'a']) count ++;//出窗口 + 维护 count，当窗口的宽度大于了 length 时，就要出窗口了            if(right - left + 1 > p.length) {char out = s[left];hash1[out - 'a']--;//出窗口后，如果 hash1 中对应的字符数量小于 hash2 中的数量，说明出的是有效的字符if(hash1[out -'a'] < hash2[out - 'a']) count--;left++;} //当 count 和 p 的长度相等时更新结果if(count == p.length) ret.add(left);right++;}return ret;}
}

2.7 串联所有单词的子串

题目链接：串联所有单词的子串

class Solution {public List<Integer> findSubstring(String s, String[] words) {List<Integer> ret = new ArrayList<>();if (words.length == 0 || s.length() < words.length * words[0].length()) return ret;// 存储 words 中每个字符串的频率Map<String, Integer> hash1 = new HashMap<>();for (String str : words) {hash1.put(str, hash1.getOrDefault(str, 0) + 1);}int len = words[0].length(), m = words.length, windowSize = len * m;// 遍历所有可能的起始点for (int i = 0; i < len; i++) {//每一次起始时，都用用一个新的 hash2 存储每个字符串的频率Map<String, Integer> hash2 = new HashMap<>();int left = i, right = i, count = 0;// 滑动窗口，要防止 right 走一步直接越界while (right + len <= s.length()) {String in = s.substring(right, right + len);right += len;// 更新窗口内单词频率计数hash2.put(in, hash2.getOrDefault(in, 0) + 1);// 如果 in 的频率不超过 hash1 中的频率，增加 countif (hash2.get(in) <= hash1.getOrDefault(in, 0)) {count++;}// 当窗口大小等于 windowSize 时出窗口if (right - left == windowSize) {if (count == m) ret.add(left); // 找到符合条件的子串String out = s.substring(left, left + len);left += len;// 更新窗口内单词频率计数if (hash2.get(out) <= hash1.getOrDefault(out, 0)) {count--;}hash2.put(out, hash2.get(out) - 1);// 如果频率为 0，从 hash2 中移除该单词if (hash2.get(out) == 0) {hash2.remove(out);}}}}return ret;}
}

2.8 最小覆盖子串

题目链接：最小覆盖子串

class Solution {public String minWindow(String ss, String tt) {// 将字符串转换成字符数组char[] s = ss.toCharArray();char[] t = tt.toCharArray();// 用 hash1 存储字符串 t 中每个字符的频率int[] hash1 = new int[128];int uniqueChars = 0; // 统计 t 中不同字符的种类数for (char ch : t) {if (hash1[ch]++ == 0) uniqueChars++;}// hash2 用来统计窗口内的字符频率int[] hash2 = new int[128];int minLen = Integer.MAX_VALUE, start = -1;int left = 0, matchedCount = 0;// 右指针移动for (int right = 0; right < s.length; right++) {char in = s[right];hash2[in]++;// 如果当前字符频率与 t 中相等，则增加匹配计数if (hash2[in] == hash1[in]) matchedCount++;// 当所有字符频率匹配时，尝试收缩窗口while (matchedCount == uniqueChars) {// 如果当前窗口更小，则更新最小窗口的长度和起始位置if (right - left + 1 < minLen) {minLen = right - left + 1;start = left;}// 出窗口char out = s[left++];if (hash2[out] == hash1[out]) matchedCount--;hash2[out]--;}}// 根据最小窗口的位置和长度返回结果return start == -1 ? "" : ss.substring(start, start + minLen);}
}