本文主要是介绍同向双指针高阶题总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
有一类题，看起来很像同向双指针，但是不完全是，一般都是求exactly K
同向双指针教会了我们如何求at most K, 现在我们要求exactly K. 那么我们可以转换为 exactly K = atMost(K) - atMost(K - 1);
这类题有好多，如下：
Subarrays with K Different Integers 思路：跟 Substrings with exactly K distinct chars ,把问题转换为 at most k的count，这样就好做，然后用公式f(k) - f(k-1); 为什么这么做转换，是因为 同向双指针是 j 一直往前面走，j不能回头的，但是这个题目要求是要求所有的 diff integer = k 的subarray；
[1,2,1,2] k = 2这个为例: [1,2], [1,2,1], [1,2,1,2], [2,1,2], [1,2] 都是答案，但是j没办法回去；所以计算是有问题的；所以不能单单扫一遍，是计算不出来的； res += j - i ; 代表的是以 j -1 为结尾的，满足at most k chars的个数；
class Solution {public int subarraysWithKDistinct(int[] A, int K) {if(A == null || A.length == 0) {return 0;}return getAtMostK(A, K) - getAtMostK(A, K - 1);}private int getAtMostK(int[] A, int k) {int res = 0;int j = 0;int count = 0;int[] counts = new int[A.length + 1];for(int i = 0; i < A.length; i++) {// move j;while(j < A.length && count <= k) {if(counts[A[j]] == 0) {if(count == k) {break;}count++;}counts[A[j]]++;j++;}// update result;res += j - i;// move i;counts[A[i]]--;if(counts[A[i]] == 0) {count--;}}return res;}
}Substrings of size K with K distinct chars 思路：这题思路很巧妙，我是看了上面那个 subarrays with k different integers 的花花视频才懂的。直接求很难，但是我们可以转换成 f(k) - f(k-1) f(k)表示最多不大于k(at most k)的char的string的个数， at most k, 可以用sliding window的双指针来做，count 就是 j - i，表示以j - 1 为尾巴的subarray的个数；
public class numberOfUniqueChars {public int getAtMostKCharacters(String s, int k) {if(s == null || s.length() == 0) {return 0;}int j = 0;int[] counts = new int[256];int c = 0;int ans = 0;for(int i = 0; i < s.length(); i++) {// move j;while(j < s.length() && c <= k) {if(counts[s.charAt(j)] == 0 ) {if(c == k) {break;}c++;}counts[s.charAt(j)]++;j++;}//update result;ans += j - i;// remove i;counts[s.charAt(i)]--;if(counts[s.charAt(i)] == 0) {c--;}}return ans;}public static void main(String[] args) {/*** Input: s = "pqpqs", k = 2Output: 7Explanation: ["pq", "pqp", "pqpq", "qp", "qpq", "pq", "qs"]* */numberOfUniqueChars numberOfUniqueChars = new numberOfUniqueChars();String s = "pqpqs";int ans1 = numberOfUniqueChars.getAtMostKCharacters(s, 2) - numberOfUniqueChars.getAtMostKCharacters(s, 1);// ans = 7;System.out.println("ans: " + ans1);}
}
Count Number of Nice Subarrays 思路：sliding window让我们学会了如何求At Most K的区间，那么Exactly K times = at most K times - at most K - 1 times
class Solution {public int numberOfSubarrays(int[] nums, int k) {if(nums == null || nums.length == 0) {return 0;}return getAtMostK(nums, k) - getAtMostK(nums, k - 1);}private int getAtMostK(int[] nums, int k) {// two pointers scan;int j = 0;int oddcount = 0;int res = 0;for(int i = 0; i < nums.length; i++) {// move j;while(j < nums.length && oddcount <= k) {if(nums[j] % 2 == 1) {if(oddcount == k) {break;}oddcount++;}j++;}//update resultres += j - i;//move i;if(nums[i] % 2 == 1) {oddcount--;}}return res;}
}
这篇关于同向双指针高阶题总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
