Two Pointers (Java) - ShuweiLeung/Thinking GitHub Wiki

该页笔记始于"2018.6.5"，结于“2018.6.6”，使用Java语言

---

1.（763:Medium）（非常经典题）Partition Labels

• 题意要求每种字母最多只出现在一个部分，所以，当我们在遍历字符串的过程中，当从某个位置i搜索到j位置，要保证[i,j]中的字母只出现在这一个范围内，才能将其分割出来，否则需要继续向后移动j指针。因此这也给出了我们解决该题的思路。
• 我们首先用一个map集合记录每个字母最后一次出现的位置，然后从头开始遍历字符串，设置lastindex来记录当前部分包含的字母的最后一个字符出现的位置，当lastindex与遍历的指针i相等时，才将其分割成一个part，然后使start遍历起点加1，开始新一部分的遍历；否则，一直将指针一直后移，最坏情况是，只将输入字符串划分为一个part，就是它自身。

该题也是greedy题目，感觉和Leetcode stack的316题相似

2.（524:Medium）（非常非常经典题）Longest Word in Dictionary through Deleting

• 该题其实主要是由两种思路，一种是对list集合d进行题目要求的规则进行排序，即长度越长、字典序越小的字符串排序位置越靠前，这样从头开始遍历，找到的第一个符合条件的字符串就是答案。另一种思路是维护一个变量longest，它代表长度最长、同时字典序最小的单词，即待返回值，每次对于符合条件的新单词都会与其进行比较并进行更新。
• 那么在完成上述的总体规划后，**如何判断某个单词是另一个字符串的subsequence呢？**在String类型题目中，我们也遇到过类似的问题，对于子序列的判断，只能是从头开始，一对一的进行比较，代码如下：

//查看是否dictWord为字符串s的subsequence，只有当前的字符串str的字符c与可能的子序列当前索引的字符相同时，i才加1
int i = 0;   //指向maySubsequence的下标索引  
for (char c : str.toCharArray()) 
    if (i < maySubsequence.length() && c == maySubsequence.charAt(i)) i++;

如何判断某个字符串str1是否为另一个字符串str2的子序列subsequence？

该次总结是受上边第2题（524）的启发，我们在判断子序列时，因为str1的相邻字符并不一定是在str2中连续位置出现的，所以我们只能使用"最原始"的方法，分别用两个指针i、j指向str1和str2，当i指向的字符与j指向的字符相等时，i才加1；而j指针无论所指字符是否与i指针字符相等，每次都会加1。

3.（838:Medium）（经典题）Push Dominoes

• 该题之所以被分为双指针问题，个人认为多米诺骨牌的关键就需要找到最近的两个向左或向右偏的位置，然后利用夹逼原则，决定出中间初始为静止竖立位置的后续状态。分情况讨论并编写代码即可，具体的分类参看代码实现。

<4>.（567:Medium）（非常非常经典题）Permutation in String

• 该题是Permutation题目，当然可以使用以前的方法，求出s1中字符所有的permutations，然后在s2中使用indexOf()来求得是否存在该permutation，否则求下一个permutation。若所有的permutation都不存在与s2中，则返回false。但显然该方法比较麻烦，也不是本体考察的重点。
• 真正的方法是使用滑动窗口思想，我们首先统计出s1中字符及出现次数的map映射集合，然后在s2中设定一个窗口，右移右边界直到某一时刻找到一个permutation或者超出了map集合中对应字符的出现次数。当出现第二种情况时，右移左边界，使重新满足map集合出现次数的条件。具体思路参看代码实现及参考链接。
• 参考链接：非常形象的滑动窗口及其本质讲解，强烈建议反复参看！

双指针的滑动窗口思想运用

滑动窗口：固定左边界不动，右移右边界。当某一时刻"窗口内的字符串不满足某一条件时"，才"向右移动左边界"，直到满足条件为止，才重新移动右边界。该"条件"往往指的是map集合中value出现次数值的大小关系，具体可以以上边第4题（567）的参考链接讲解为例。

5.（826:Medium）（非常经典题）Most Profit Assigning Work

• 该题其实难度并不大，只需要让每个worker做尽量大难度的任务而且该任务的收益还必须尽量高，同时，为了一次遍历的同时确定每个人的具体任务，我们需要从worker最小的数开始，因此要将worker数组排序，这样后面的worker一定会比之前的worker能做的任务难度大，且收益可能也会多，便能一次便利获取所有worker的最大总收益。但需要注意几点：1. worker数组不一定顺序排列，因此要排序 2. difficulty数组不一定有序，但difficulty和profit对应位置一定正确，因此要用map绑定难度和收益，并根据难度排序 3. 可能某两个任务的难度相同而收益不同，这样在建立map集合时要记录收益大的那个任务
• 参考链接：花花讲解，包括另一种Greedy思路

6.（845:Medium）（经典题）Longest Mountain in Array

• 该题其实类似于滑动窗口，我们固定左边界不动，一直向右移动右窗口，在保证当前[left,right]之间有一个最高点的时候，若再次出现上升趋势的序列，则要比较当前mountain的长度与之前的最长长度并更新，然后将左边界移动到当前上升序列开始的第一个元素位置，继续新的搜索。若当前窗口内全是递减序列，则将左边界右移，即窗口向右滑动。

7.（828:Hard）（非常经典题）Unique Letter String

• 如果考虑每一个子串，那么不仅情况很多，而且非常耗时，一定会超时。参看discuss，正确的方法是"变换一种思路"：与其考虑每个字符串中有哪些distinct字符，不如考虑让每一个字符若成为子串中的distinct字符，有多少个符合条件的子串。具体思路见下，实现过程请参看代码：

Intuition:

Let's think about how a character can be found as a unique character.

Think about string "XAXAXXAX" and focus on making the second "A" a unique character.

We can take "XA(XAXX)AX" and between "()" is our substring.

We can see here, to make the second "A" counted as a uniq character, we need to:

1. insert "(" somewhere between the first and second A
2. insert ")" somewhere between the second and third A

For step 1 we have "A(XA" and "AX(A", 2 possibility.

For step 2 we have "A)XXA", "AX)XA" and "AXX)A", 3 possibilities.

So there are in total 2 * 3 = 6 ways to make the second A a unique character in a substring.

In other words, there are only 6 substring, in which this A contribute 1 point as unique string.

Instead of counting all unique characters and struggling with all possible substrings, we can count for every char in S, how many ways to be found as a unique char. We count and sum, and it will be out answer. * Explanation:

1. index[26][2] record last two occurrence index for every upper characters.记录当前字符之前出现的最后两次位置
2. Initialise all values in index to -1.
3. Loop on string S, for every character c, update its last two occurrence index to index[c].
4. Count when loop. For example, if "A" appears once at index 3, 6, 9 seperately, we need to count:

        For the first "A": (6-3) * (3-(-1))"
        For the second "A": (9-6) * (6-3)"
        For the third "A": (N-9) * (9-6)"

8.（395:Hard）（非常非常经典题）Longest Substring with At Least K Repeating Characters

• In each step, just find the infrequent elements (show less than k times) as splits since any of these infrequent elements couldn't be any part of the substring we want.

    public int longestSubstring(String s, int k) {
        if (s == null || s.length() == 0) return 0;
        int[] chars = new int[26];
        // record the frequency of each character
        for (int i = 0; i < s.length(); i += 1) chars[s.charAt(i) - 'a'] += 1;
        boolean flag = true;
        for (int i = 0; i < chars.length; i += 1) {
            if (chars[i] < k && chars[i] > 0) flag = false;
        }
        // return the length of string if this string is a valid string
        if (flag == true) return s.length();
        int result = 0;
        int start = 0, cur = 0;
        // otherwise we use all the infrequent elements as splits
        while (cur < s.length()) {
            if (chars[s.charAt(cur) - 'a'] < k) {
                result = Math.max(result, longestSubstring(s.substring(start, cur), k));
                start = cur + 1;
            }
            cur++;
        }
        result = Math.max(result, longestSubstring(s.substring(start), k));
        return result;
    }

9.（904:Medium）（非常经典题）Fruit Into Baskets

• 该题应该算作比较典型的滑动窗口问题（双指针），我们用一个变量types记录当前窗口内的fruit种类，当fruit种类达到两个时，我们就右移左边界，删除左边界指向的fruit直到当前篮子里只有一种水果，然后我们再将新水果加入篮子中，每次循环都需要更新res变量。具体思路可以参看代码实现

10.（986:Medium）（非常经典题）Interval List Intersections

• 该题维护两个指针分别指向A和B数组，当当前的两个区间有相交时，将interception加入res结果集中，然后比较两个区间结束的位置，将结束位置靠前的指针向后移动一个单位。

11.（1004:Medium）（非常非常经典题）Max Consecutive Ones III

• 该题可以转化为，寻找包含最多K个0的最长subarray。参考代码如下(含注释)：

//维持一个窗口，统计窗口中0的个数，保证窗口中0的个数小于等于K
public int longestOnes(int[] A, int K) {
    int i = 0, j; //窗口的两个边界
    int res = 0; //最长连续0的个数
    for (j = 0; j < A.length; ++j) {
        if (A[j] == 0) K--; //当当前j指向的元素为0时，将K减一
        if(K < 0){ //如果K<0,说明窗口中的0个数超标，需要移动左边界
            while(A[i] != 0){ //找到i后边的第一个0位置
                i++;
            }
            //此时i指向的是后面的第一个0，略去
            i++; //移向当前0的下一位
            K++;
        }
        res = Math.max(res, j - i + 1); //更新res变量
    }
    return res;
}

12.（992:Hard）（非常非常经典题）Subarrays with K Different Integers

• First you may have feeling of using sliding window. Then this idea get stuck in the middle.
• This problem will be a very typical sliding window, if it asks the number of subarrays with at most K distinct elements.
• Just need one more step to reach the folloing equation: exactly(K) = atMost(K) - atMost(K-1)。因为最多K个不同的数字和最多K-1个不同的数字，这两种情况的数量相差的就是正好为K个不同数字的情况。

13.（923:Medium）（非常经典题）3Sum With Multiplicity

• 先统计每个数组元素的频率，然后按照排列组合知识统计各种情况的个数，并将其求和。
• 参考链接：花花视频讲解

//感觉下面的解法默认数组A是升序排列的？为什么不care索引的关系
public int threeSumMulti(int[] A, int target) {
    long[] c = new long[101]; // A[i]的范围在0 <= A[i] <= 100
    for (int a : A) c[a]++; //统计数组中每个数字的频率
    long res = 0; //可能的组合个数
    // 为了避免重复，i <= j <= k
    for (int i = 0; i <= 100; i++)
        for (int j = i; j <= 100; j++) { // i <= j
            int k = target - i - j; // A[k] = target - A[i] - A[j].
            if (k > 100 || k < 0) continue;
            if (i == j && j == k) // 组合数公式，从一堆相同的数中任意选取3个
                res += c[i] * (c[i] - 1) * (c[i] - 2) / 6;
            else if (i == j && j != k) // 组合数公式，从一堆相同的数中任意选取2个
                res += c[i] * (c[i] - 1) / 2 * c[k];
            else if (j < k) // i <= j < k, k < j是不合法的
                res += c[i] * c[j] * c[k];
        }
    return (int)(res % (1e9 + 7));
}