双指针

给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。 初始化 A 和 B 的元素数量分别为 m 和 n。 示例: 输入: A = [1,2,3,0,0,0], m = 3 B = [2,5,6], n = 3 输出: [1,2,2,3,5,6] class Solution { public void merge(int[] A, int m, int[] B, int n) { for (int i = 0; i != n; ++i) { A[m + i] = B[i]; } Arrays.sort(A); } } 作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/sorted-merge-lcci/solution/mian-shi-ti-1001-he-bing-pai-xu-de-shu-zu-by-leetc/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。 说明： 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。 示例： 输入： nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 输出：[1,2,2,3,5,6] /** * @param {number[]} nums1 * @param {number} m * @param {number[]} nums2 * @param {number} n * @return {void} Do not return anything, modify nums1 in-place instead. */ var merge = function(nums1, m, nums2, n) { let len1 = m - 1; let len2 = n - 1; let len = m + n - 1; while(len1 >= 0 && len2 >= 0) { // 注意--符号在后面，表示先进行计算再减1，这种缩写缩短了代码 nums1[len--] = nums1[len1] > nums2[len2] ? nums1[len1--] : nums2[len2--]; } function arrayCopy(src, srcIndex, dest, destIndex, length) { dest.splice(destIndex, length, ...src.slice(srcIndex, srcIndex + length)); } // 表示将nums2数组从下标0位置开始，拷贝到nums1数组中，从下标0位置开始，长度为len2+1 arrayCopy(nums2, 0, nums1, 0, len2 + 1); }; 作者：guanpengchn 链接：https://leetcode-cn.com/problems/merge-sorted-array/solution/hua-jie-suan-fa-88-he-bing-liang-ge-you-xu-shu-zu-/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。 注意：如果对空文本输入退格字符，文本继续为空。 示例 1： 输入：S = "ab#c", T = "ad#c" 输出：true 解释：S 和 T 都会变成 “ac”。 示例 2： 输入：S = "ab##", T = "c#d#" 输出：true 解释：S 和 T 都会变成 “”。 示例 3： 输入：S = "a##c", T = "#a#c" 输出：true 解释：S 和 T 都会变成 “c”。 示例 4： 输入：S = "a#c", T = "b" 输出：false 解释：S 会变成 “c”，但 T 仍然是 “b”。 function* reversed(v: string) { for (let p = v.length - 1; p >= 0; --p) { for (let q = 0; v[p] === # || q; --p) { q += v[p] === #? 1: -1 } yield v[p] } } function backspaceCompare(S: string, T: string): boolean { let s = reversed(S), t = reversed(T) while (true) { let i = s.next().value, j = t.next().value if (i === j && i === undefined) { return true } else if (i === j) { continue } else { return false } } }; 作者：tuotuoli 链接：https://leetcode-cn.com/problems/backspace-string-compare/solution/844-bi-jiao-han-tui-ge-de-zi-fu-chuan-by-tuotuoli/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 自己实现 let a = "ab#c" let arr = a.split() let iteration = function(arr){ if(!arr.includes(#)) return arr let result = arr.reduce((pre,cur)=>{ if(cur !== #){ return pre = pre } else { debugger let spliceIndex = !pre.indexOf(cur) ? 0 : pre.indexOf(cur)-1 pre.splice(spliceIndex,1) if(spliceIndex){ pre.splice(spliceIndex,1) } return pre = pre } },arr) return iteration(result) }

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。 说明：本题中，我们将空字符串定义为有效的回文串。 示例 1: 输入: "A man, a plan, a canal: Panama" 输出: true 示例 2: 输入: "race a car" 输出: false /** * @param {string} s * @return {boolean} */ var isPalindrome = function(s) { // 正则去除非单词字符和下划线，然后转化为小写字符 let str = s.replace(/(\W|_)/g, ).toLocaleLowerCase() // 下面就是用双指针判断是否是回文字符串的过程了 let left = 0 let right = str.length - 1 while (left < right) { if (str[left] !== str[right]) { return false } left++ right-- } return true } 作者：cchroot-liu 链接：https://leetcode-cn.com/problems/valid-palindrome/solution/zheng-ze-shuang-zhi-zhen-by-cchroot-9/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 示例: 输入: [0,1,0,3,12] 输出: [1,3,12,0,0] // 双指针实现（快慢指针） // 时间复杂度 O(n) // 空间复杂度 O(1) public void moveZeroes2(int[] nums) { if (nums == null || nums.length == 0) { return; } int slow = 0; for (int fast = 0; fast < nums.length; fast++) { if (nums[fast] != 0) { if (slow != fast) { // 减少交换的次数 // 交换 fast 和 slow 指向的元素 int tmp = nums[fast]; nums[fast] = nums[slow]; nums[slow] = tmp; } slow++; } } } 作者：tangweiqun 链接：https://leetcode-cn.com/problems/move-zeroes/solution/pei-yang-suan-fa-si-wei-cong-bao-li-ceng-c24w/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 优化： public void moveZeroes(int[] nums) { if (nums == null || nums.length == 0) { return; } int slow = 0; for (int fast = 0; fast < nums.length; fast++) { if (nums[fast] != 0) { if (slow != fast) { // 减少赋值的次数 nums[slow] = nums[fast]; } slow++; } } for (; slow < nums.length; slow++) { nums[slow] = 0; } } 作者：tangweiqun 链接：https://leetcode-cn.com/problems/move-zeroes/solution/pei-yang-suan-fa-si-wei-cong-bao-li-ceng-c24w/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

实现 strStr() 函数。 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。 示例 1: 输入: haystack = "hello", needle = "ll" 输出: 2 示例 2: 输入: haystack = "aaaaa", needle = "bba" 输出: -1 public class KMP { private int[][] dp; private String pat; public KMP(String pat) { this.pat = pat; int M = pat.length(); // dp[状态][字符] = 下个状态 dp = new int[M][256]; // base case dp[0][pat.charAt(0)] = 1; // 影子状态 X 初始为 0 int X = 0; // 构建状态转移图（稍改的更紧凑了） for (int j = 1; j < M; j++) { for (int c = 0; c < 256; c++) { dp[j][c] = dp[X][c]; dp[j][pat.charAt(j)] = j + 1; // 更新影子状态 X = dp[X][pat.charAt(j)]; } } public int search(String txt) { int M = pat.length(); int N = txt.length(); // pat 的初始态为 0 int j = 0; for (int i = 0; i < N; i++) { // 计算 pat 的下一个状态 j = dp[j][txt.charAt(i)]; // 到达终止态，返回结果 if (j == M) return i - M + 1; } // 没到达终止态，匹配失败 return -1; } } 作者：labuladong 链接：https://leetcode-cn.com/problems/implement-strstr/solution/kmp-suan-fa-xiang-jie-by-labuladong/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。 示例 1: 给定数组 nums = [1,1,2], 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 你不需要考虑数组中超出新长度后面的元素。 示例 2: 给定 nums = [0,0,1,1,1,2,2,3,3,4], 函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。 你不需要考虑数组中超出新长度后面的元素。 说明: 为什么返回数值是整数，但输出的答案是数组呢? 请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。 你可以想象内部操作如下: // nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝 int len = removeDuplicates(nums); // 在函数里修改输入数组对于调用者是可见的。 // 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。 var removeDuplicates = function(nums) { var i = 0; for(let j = 1;j<nums.length;j++){ if(nums[i]!=nums[j]){ i++; nums[i] = nums[j]; } } return i+1; }; console.log(removeDuplicates([0,0,1,1,1,2,2,3,3,4])) https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/solution/shi-ping-dong-hua-jie-xi-bao-ni-dong-by-novice2mas/

我们把数组 A 中符合下列属性的任意连续子数组 B 称为 “山脉”： B.length >= 3 存在 0 < i < B.length - 1 使得 B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1] （注意：B 可以是 A 的任意子数组，包括整个数组 A。） 给出一个整数数组 A，返回最长 “山脉” 的长度。 如果不含有 “山脉” 则返回 0。 示例 1： 输入：[2,1,4,7,3,2,5] 输出：5 解释：最长的 “山脉” 是 [1,4,7,3,2]，长度为 5。 示例 2： 输入：[2,2,2] 输出：0 解释：不含 “山脉”。 /** * 941. 有效的山脉数组 LeetCode Easy * @param A * @return */ public boolean validMountainArray(int[] A) { if (A == null || A.length < 3) { return false; } int n = A.length - 1; int l = 0, r = n; while (l < n) { if (A[l] < A[l + 1]) { l++; } else { break; } } while (r >= 1) { if (A[r] < A[r - 1]) { r--; } else { break; } } return l > 0 && r < n && l == r; } 作者：a-fei-8 链接：https://leetcode-cn.com/problems/longest-mountain-in-array/solution/leetcode-shan-feng-shu-zu-san-ti-by-a-fei-8/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 变形二： 852. 山脉数组的峰顶索引 LeetCode Easy [Binary Search] public int peakIndexInMountainArray(int[] A) { int l = 1, r = A.length - 1; while (l < r) { int mid = l + (r - l) / 2; if (A[mid] > A[mid - 1] && A[mid] < A[mid + 1]) { l = mid + 1; } else { r = mid; } } return l; } 作者：a-fei-8 链接：https://leetcode-cn.com/problems/longest-mountain-in-array/solution/leetcode-shan-feng-shu-zu-san-ti-by-a-fei-8/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 变形三: 数组中的最长山脉 LeetCode Medium [Two Pointers] /** * 845. 数组中的最长山脉 LeetCode Medium * * @param A * @return */ public int longestMountain(int[] A) { if (A == null || A.length < 3) { return 0; } int res = 0; for (int i = 1; i < A.length - 1; i++) { //find the maxium number [peak mountain] if (A[i] > A[i - 1] && A[i] > A[i + 1]) { //get the left pointer and right pointer, expand from the center ,get the maximum boundary int l = i - 1; int r = i + 1; while (l > 0 && A[l - 1] < A[l]) { l--; } while (r < A.length - 1 && A[r] > A[r + 1]) { r++; } //record the maximum len res = Math.max(res, r - l + 1); } } return res; } 作者：a-fei-8 链接：https://leetcode-cn.com/problems/longest-mountain-in-array/solution/leetcode-shan-feng-shu-zu-san-ti-by-a-fei-8/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。 注意：答案中不可以包含重复的三元组。 示例： 给定数组 nums = [-1, 0, 1, 2, -1, -4]， 满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ] const threeSum = (nums) => { nums.sort((a, b) => a - b); // 排序 const res = []; for (let i = 0; i < nums.length - 2; i++) { // 外层遍历 let n1 = nums[i]; if (n1 > 0) break; // 如果已经爆0，不用做了，break if (i - 1 >= 0 && n1 == nums[i - 1]) continue; // 遍历到重复的数，跳过 let left = i + 1; // 左指针 let right = nums.length - 1; // 右指针 while (left < right) { let n2 = nums[left], n3 = nums[right]; if (n1 + n2 + n3 === 0) { // 三数和=0，加入解集res res.push([n1, n2, n3]); while (left < right && nums[left] == n2) left++; // 直到指向不一样的数 while (left < right && nums[right] == n3) right--; // 直到指向不一样的数 } else if (n1 + n2 + n3 < 0) { // 三数和小于0，则左指针右移 left++; } else { // 三数和大于0，则右指针左移 right--; } } } return res; }; 作者：xiao_ben_zhu 链接：https://leetcode-cn.com/problems/3sum/solution/zhi-zhen-yi-dong-guo-cheng-zhong-tiao-guo-zhong-fu/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。 注意: 字符串长度 和 k 不会超过 104。 示例 1: 输入: s = "ABAB", k = 2 输出: 4 解释: 用两个A替换为两个B,反之亦然。 示例 2: 输入: s = "AABABBA", k = 1 输出: 4 解释: 将中间的一个A替换为B,字符串变为 "AABBBBA"。 子串 "BBBB" 有最长重复字母, 答案为 4。 var characterReplacement = function(s, k) { let maxChar = 0, start = 0, maxLength = 0 let map = {} for (let i = 0; i < s.length; i++) { const char = s[i] if (!map[char]) { map[char] = 0 } map[char] += 1 // 计算最大重复的字符 maxChar = Math.max(maxChar, map[char]) // 当前遍历过字符的长度如果大于最大重复字符 + 可替换的字符 K，就左移窗口 if (i - start + 1 - maxChar > k) { const startChar = s[start++] map[startChar] -= 1 } maxLength = Math.max(maxLength, i - start + 1) } return maxLength }; 作者：yck 链接：https://leetcode-cn.com/problems/longest-repeating-character-replacement/solution/chao-hao-dong-ti-jie-by-yck/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

给定两个整数数组a和b，计算具有最小差绝对值的一对数值（每个数组中取一个值），并返回该对数值的差 示例： 输入：{1, 3, 15, 11, 2}, {23, 127, 235, 19, 8} 输出： 3，即数值对(11, 8) /** * @param {number[]} a * @param {number[]} b * @return {number} */ var smallestDifference = function (a, b) { let item = Math.abs(a[0] - b[0]) for( let i = 0 ; i < a.length ; i++ ){ for( let j = 0 ; j < b.length ; j++ ){ if( Math.abs(a[i] - b[j]) < item ){ item = Math.abs(a[i] - b[j]) } } } return item }; 作者：eleven_xie 链接：https://leetcode-cn.com/problems/smallest-difference-lcci/solution/-by-eleven_xie-215/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。 返回仅包含 1 的最长（连续）子数组的长度。 示例 1： 输入：A = [1,1,1,0,0,0,1,1,1,1,0], K = 2 输出：6 解释： [1,1,1,0,0,1,1,1,1,1,1] 粗体数字从 0 翻转到 1，最长的子数组长度为 6。 示例 2： 输入：A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3 输出：10 解释： [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1] 粗体数字从 0 翻转到 1，最长的子数组长度为 10。 /** * @param {number[]} A * @param {number} K * @return {number} */ var longestOnes = function(A, K) { var left=right=count=max=0; while(right<A.length){ if(A[right]==0){ count++; } while(count>K){ if(A[left]==0){ left++; count--; }else{ left++; } } max = Math.max(max,right-left+1); right++; } return max; }; 作者：cctt-2 链接：https://leetcode-cn.com/problems/max-consecutive-ones-iii/solution/hua-dong-chuang-kou-by-cctt-2-2/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。 说明：你不能倾斜容器。 示例 1： 输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。 示例 2： 输入：height = [1,1] 输出：1 示例 3： 输入：height = [4,3,2,1,4] 输出：16 示例 4： 输入：height = [1,2,1] 输出：2 var removeDuplicates = function(nums) { let i = 0; let j = nums.length -1 let maxArea = 0; let area = 0 while(i<j){ if(nums[i]<=nums[j]){ area = (j-i) * nums[i] i++ } else { area = (j-i)*nums[j] j++ } maxArea = Math.max(area,maxArea) } return maxArea }; console.log(removeDuplicates([0,0,1,1,1,2,2,3,3,4])) https://leetcode-cn.com/problems/container-with-most-water/solution/bu-yong-kua-wo-jiu-shi-zhe-yao-shuai-by-novice2mas/ 链接：https://leetcode-cn.com/problems/container-with-most-water/solution/shuang-zhi-zhen-fa-wu-chong-yu-yan-by-ml-zimingmen/

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。 示例： 输入：nums = [-1,2,1,-4], target = 1 输出：2 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。 class Solution { public int threeSumClosest(int[] nums, int target) { Arrays.sort(nums); int ans = nums[0] + nums[1] + nums[2]; for(int i=0;i<nums.length;i++) { int start = i+1, end = nums.length - 1; while(start < end) { int sum = nums[start] + nums[end] + nums[i]; if(Math.abs(target - sum) < Math.abs(target - ans)) ans = sum; if(sum > target) end--; else if(sum < target) start++; else return ans; } } return ans; } } 作者：guanpengchn 链接：https://leetcode-cn.com/problems/3sum-closest/solution/hua-jie-suan-fa-16-zui-jie-jin-de-san-shu-zhi-he-b/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。 注意： 答案中不可以包含重复的四元组。 示例： 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ] 回溯算法： 一 var fourSum = function(nums, target) { let res=[] let path=[] nums.sort() let backtrace=(start)=>{ if((path.length==4)){ if(path[0]+path[1]+path[2]+path[3]==target){ res.push([...path]) } return; } for(let i=start;i<nums.length;i++){ if(nums[i]==nums[i-1]&&i>start){ continue; } path.push(nums[i]) backtrace(i+1); path.pop() } } backtrace(0) return res; }; 作者：ther-roselia 链接：https://leetcode-cn.com/problems/4sum/solution/you-yi-dao-ti-kan-hui-su-fa-de-ge-chong-jian-zhi-j/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 双指针算法: public List<List<Integer>> fourSum(int[] nums, int target) { if (nums == null || nums.length < 4) return new ArrayList<>(); Arrays.sort(nums); List<List<Integer>> res = new ArrayList<>(); // O(n^3) for (int i = 0; i < nums.length - 3; i++) { // 忽略后面与前面重复的元素 if (i > 0 && nums[i] == nums[i - 1]) continue; for (int j = i + 1; j < nums.length - 2; j++) { // 忽略后面与前面重复的元素 if (j > i + 1 && nums[j] == nums[j - 1]) continue; int partSum = nums[i] + nums[j]; int left = j + 1; int right = nums.length - 1; while (left < right) { int sum = partSum + nums[left] + nums[right]; if (sum > target) { right--; } else if (sum < target) { left++; } else { res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right])); while (left < right && nums[left] == nums[++left]); while (left < right && nums[right] == nums[--right]); } } } } return res; } 作者：tangweiqun 链接：https://leetcode-cn.com/problems/4sum/solution/suan-fa-si-wei-yang-cheng-ji-shuang-zhi-539ll/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。 示例： 输入：s = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。 public int minSubArrayLen(int s, int[] nums) { if (nums.length == 0) { return 0; } // window [start...end] int start = 0; int end = -1; int sum = 0; int result = nums.length + 1; while (start < nums.length) { // 还有剩余元素未考察并且窗口内元素总和小于目标值s if (end + 1 < nums.length && sum < s) { end++; sum += nums[end]; } else { // 尝试缩小窗口 sum -= nums[start]; start++; } ​ // 窗口内元素总和大于等于目标值s则更新结果值 if (sum >= s) { result = Math.min(result, end - start + 1); } } ​ return result == nums.length + 1 ? 0 : result; } 作者：hardcore-aryabhata 链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum/solution/hua-dong-chuang-kou-209-chang-du-zui-xia-ljne/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 作者：fo-qian-xiu-luo-se 链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum/solution/209shuang-zhi-zhen-hua-dong-chuang-kou-by-fo-qian-/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 进阶： 你可以不使用代码库中的排序函数来解决这道题吗？ 你能想出一个仅使用常数空间的一趟扫描算法吗？ 示例 1： 输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2] 示例 2： 输入：nums = [2,0,1] 输出：[0,1,2] 示例 3： 输入：nums = [0] 输出：[0] 示例 4： 输入：nums = [1] 输出：[1] class Solution { public void sortColors(int[] nums) { int n = nums.length; int p0 = 0, p1 = 0; for (int i = 0; i < n; ++i) { if (nums[i] == 1) { int temp = nums[i]; nums[i] = nums[p1]; nums[p1] = temp; ++p1; } else if (nums[i] == 0) { int temp = nums[i]; nums[i] = nums[p0]; nums[p0] = temp; if (p0 < p1) { temp = nums[i]; nums[i] = nums[p1]; nums[p1] = temp; } ++p0; ++p1; } } } } 作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/sort-colors/solution/yan-se-fen-lei-by-leetcode-solution/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。 换句话说，第一个字符串的排列之一是第二个字符串的子串。 示例1: 输入: s1 = "ab" s2 = "eidbaooo" 输出: True 解释: s2 包含 s1 的排列之一 ("ba"). 示例2: 输入: s1= "ab" s2 = "eidboaoo" 输出: False /** * @param {string} s1 * @param {string} s2 * @return {boolean} */ var checkInclusion = function(s1, s2) { let left = 0,right = 0; let needs = {},windows = {}; let match = 0; for(let i = 0;i < s1.length;i++){ needs[s1[i]] ? needs[s1[i]]++ : needs[s1[i]] = 1; } let needsLen = Object.keys(needs).length; while(right < s2.length){ let c1 = s2[right]; if(needs[c1]){ windows[c1] ? windows[c1]++ : windows[c1] = 1; if(windows[c1] === needs[c1]){ match++; } } right++; while(match === needsLen){ if(right - left === s1.length){ return true; } let c2 = s2[left]; if(needs[c2]){ windows[c2]--; if(windows[c2] < needs[c2]){ match--; } } left++; } } return false; }; 作者：Alexer-660 链接：https://leetcode-cn.com/problems/permutation-in-string/solution/567-zi-fu-chuan-de-pai-lie-by-alexer-660/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。