美柑の部屋

涙は見せないと誓った。

Loading…

面试常见问题盘点：双指针

在关于数组的问题中，有那么一类问题，它们可以利用双指针（Two Pointers）方法解决。需要说明的一点是，这里提到的“指针”不一定指的是严格意义上的指针，在很多场合下，它被用来代指用来进行遍历的下标i或j。所以“双指针”问题其实就是利用两个下标i和j对数组进行遍历的一类问题。本文就来列举一部分面试中经常涉及到的“双指针”问题。

类别一

1、Two Sum问题

问题：输入一个排好序的int类型数组arr，以及一个整数target。判断arr中是否存在两个元素，它们的和等于target。
解法：这个问题是双指针问题中比较基础并且比较典型的一类问题了。我们定义两个指针i和j，分别从数组的左右端点开始遍历，在遍历时，观察arr[i]和arr[j]的和sum。如果sum > target，则j--；如果sum < target，则i++。如果i和j已经相遇但是仍未找到答案，则说明原数组不存在这样的两个元素。
分析：相比起O(n2)的暴力解法，双指针的方法进行了剪枝，将时间复杂度减少到了O(n)。

2、判断一个字符串是否是回文字符串

问题：输入一个字符串str，判断它是不是回文字符串。
解法：仍然是定义两个指针i和j，分别从字符串的左右端点开始遍历。在每个迭代中，观察str[i]和str[j]是否相等，并且令i右移一格、j左移一格，直到两个指针相遇。
分析：同类的题目还有在O(n)时间内原地反转字符串等。

3、容积最大的容器

问题：Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water. Note: You may not slant the container.
解法：暴力解法的时间复杂度为O(n2)，能不能像前面提到的Two Sum问题一样进行剪枝呢？答案是肯定的。
我们在遍历的过程中用maxWater记录当前最大的容积。假设容器的两条边是0和n-1号，我们可以算出一个容量F(0,n-1) = height[0] * (n-1)，将其作为maxWater的初始值。
我们注意到：如果0号边的高度不大于n-1号边的高度，所有以0号边为左侧边的容器容积都比F(0,n-1)小。因为所有这样的容器高度肯定不大于height[0]，但是宽度却一定小于n-1，所以其容积肯定小于F(0,n-1)，所以我们不需要对这些情况进行枚举。同理，如果0号边的高度大于n-1号边的高度，我们就不需要对其他以n-1号边作为右侧边的容器进行枚举了。
这样我们就完成了剪枝。我们定义两个指针i和j，分别从数组的左右端点开始遍历。每个迭代，先算出F(i,j)并更新maxWater的值，然后根据前面得出的结论：如果height[i]不大于height[j]，直接i++；否则直接j--。显然，这种方法的时间复杂度是O(n)。

Container With Most Water 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

int maxArea(vector<int>& height) {
    if(height.size() <= 1)
        return 0;

    int p1 = 0;
    int p2 = height.size() - 1;
    int maxWater = 0;
    while(p1 < p2){
        maxWater = max(maxWater, min(height[p1], height[p2]) * (p2-p1));
        if(height[p1] <= height[p2])
            p1++;
        else
            p2--;
    }
    return maxWater;
}

总结

这一类的双指针问题有一个共同之处：分别从数组的左右端点开始遍历。其中，问题二需要这样做，是因为需要研究字符串本身的对称性；问题一和问题三需要这样做，是对暴力搜索进行剪枝的结果。

类别二

1、删除数组中所有值等于val的元素

问题：Given an array and a value, remove all instances of that value in place and return the new length. Note: The order of elements can be changed. It doesn’t matter what you leave beyond the new length.
解法：通常我们会使用一个新的数组来存储那些不被删除的数，这样就能够很顺利的完成任务。但是实际上由于在这个过程中，新数组的大小是肯定会小于原本数组中已经处理过的数的数量的，所以我们就可以直接利用原本数组中已经处理过的数的位置，避免再开一个额外的数组。所以这里就用到了一种思想，定义两个指针i和cnt，i是遍历用的指针，cnt指向新数组的下一个位置。每当i遍历到一个符合条件的元素，就通过arr[cnt++] = arr[i]将其加入到新数组中。此方法的时间复杂度是O(n)。

Remove Element 
1
2
3
4
5
6
7
8
9

int removeElement(vector<int>& nums, int val) {
    int cnt = 0;
    for(int i = 0; i < nums.size(); i++)
    {
        if(nums[i] != val)
            nums[cnt++] = nums[i];
    }
    return cnt;
}

2、奇偶分类

问题：输入一个数组，将其进行重排，使得所有奇数位于所有偶数的前面。
解法：我们定义两个指针i和j，其中j是遍历用的指针，i则记录了当前数组奇数部分的下一个位置。每当j遍历到一个奇数时，就交换arr[i]和arr[j]的值，然后i++。这样当数组遍历完毕后，arr[0..i-1]就存储了所有的奇数，剩下的部分则存储了所有的偶数。

Classify Odd And Even Numbers 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

int main() {
    int num;
    cin >> num; //输入数组长度
    vector<int> arr(num);
    for (int j = 0; j < num; j++) //依次输入数组元素
        cin >> arr[j];

    int i = 0; //奇数部分的下一个位置
    for (int j = 0; j < num; j++) {
        if (arr[j] & 0x1) {
            int tmp = arr[j];
            arr[j] = arr[i];
            arr[i] = tmp;
            i++;
        }
    }
    for (int j = 0; j < num; j++)
        cout << arr[j] << ' ';
}

3、替换空格

问题：实现一个函数，把字符串中的每个空格都替换成"%20"。
解法：如果是暴力解法，从前往后遍历字符串，在遍历到空格的时候，就将后面的所有字符后移两格，这样的方法在最坏情况下（字符串中都是空格）是O(n2)的。我们有更快的解法，其时间复杂度为O(n)，每个字符只需要向后移动一次，那就是“从后往前替换字符串”。
首先遍历一遍原字符串确认有多少个空格，这样我们就得到了新字符串的长度。然后我们令p1从原字符串的末尾往前遍历，p2指向新字符串中已经被替换好的部分的前一个元素。如果arr[p1]不是空格，直接将其拷贝到arr[p2]的位置，然后p2左移一格；如果arr[p1]是空格，则在p2位置依次插入0、2和%。

Replace Space 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

void replaceSpace(string& arr){
    int spaceCount = 0;
    for(int i=0; i<arr.size(); i++)
        if(arr[i] == ' ')
            spaceCount++;

    int p1 = arr.size() - 1;
    for(int i=0; i<2*spaceCount; i++)
        arr.push_back(' ');

    int p2 = arr.size() - 1;
    while(p2 >= 0){
        if(arr[p1] != ' '){
            arr[p2] = arr[p1];
            p1--, p2--;
        }else{
            arr[p2--] = '0';
            arr[p2--] = '2';
            arr[p2--] = '%';
            p1--;
        }
    }
}

总结

这一类的双指针问题有一个共同之处：其中一个指针用于遍历，另一个指针指向数组已完成部分的下一个元素。这种方法可以节省空间，或者减少数据重复移动的次数。

类别三

1、无重复字符的最长子字符串

问题：Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.
解法：利用p1和p2两个指针构成一个窗口，其中p1指向窗口的第一个元素，p2指向窗口最后一个元素的下一个元素。我们利用一个hashmap记录窗口中各个字符的出现次数，并且保证窗口中没有重复字符。
具体做法是：观察即将加入窗口中的字符str[p2]。如果该字符没有在窗口中出现过，我们可以直接将该字符加入窗口中，即p2++，同时调整hashmap的记录；如果该字符在窗口中出现过，那么我们令p1++来缩小窗口的大小，同时调整hashmap的记录，直到该字符没有在窗口中出现为止。在遍历的过程中，记录窗口达到的最大长度。算法的时间复杂度为O(n)。

Longest Substring Without Repeating Characters 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

int lengthOfLongestSubstring(string s) {
    if(s.size() == 0)
        return 0;

    int p1 = 0;
    int p2 = 1;
    int size = s.size();
    unordered_map<char, int> hashmap;
    hashmap[s[p1]]++; //首元素加入哈希表。

    int maxLength = 1;
    int curLength = 1;
    while(p2 < size){
        if(hashmap[s[p2]] == 0){
            hashmap[s[p2]]++;
            p2++;
            curLength++;
            maxLength = max(maxLength, curLength);
        }else{
            hashmap[s[p1]]--;
            p1++;
            curLength--;
        }
    }
    return maxLength;
}

2、Minimum Window Substring

问题：Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). For example,
S = “ADOBECODEBANC”
T = “ABC”
Minimum window is "BANC".
Note: If there is no such window in S that covers all characters in T, return the empty string "". If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
解法：我们仍然利用两个指针p1和p2组成一个窗口，其中p1指向窗口的第一个元素，p2指向窗口最后一个元素的下一个元素。我们还要定义一个哈希表set，表示T中出现过哪些字符，如果遍历到没有在T中出现过的字符，我们可以将该字符跳过，继续遍历下一个字符。
为了记录窗口中的字符和T中字符的匹配情况，我们定义一个整数count，表示T中待匹配的字符数量，count等于0说明T中所有字符都已经匹配上；另外，定义一个哈希表num，表示每个字符的待匹配次数，比如当num['a']等于2时，说明窗口中还要再包括进两个'a'才能满足题意。需要注意的是，num中字符对应的待匹配次数可以为负，负数说明该字符过匹配（出现次数太多了）。

在每次遍历中，我们首先检查count是否大于0。
如果count大于0，说明还有字符待匹配，我们需要将s[p2]加入到窗口中，并且令num[s[p2]]--。如果该字符还没有过匹配（num[s[p2]]>=0），那么将该字符加入窗口后，待匹配的字符数量减少1，所以count--；如果s[p2]过匹配（num[s[p2]]<0），那么将该字符加入窗口后并不能使待匹配的字符数量减少，所以count不发生变化。
如果count等于0，说明已经找到了一个符合题意的窗口，我们需要将记录当前窗口的长度，然后继续向下搜索：从窗口中取出s[p1]，并且令num[s[p1]]++。如果发现num[s[p1]]>0，说明该字符从匹配状态变成了未匹配状态，所以待匹配的字符数量增加1，即count++；如果发现num[s[p1]]<=0，说明该字符仍是匹配状态，待匹配的字符数量并没有增加，所以count不发生变化。

Minimum Window Substring 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

string minWindow(string s, string t) {
    if(s.size() == 0 || t.size() == 0)
        return "";

    unordered_map<char, int> charNum;
    unordered_map<char, int> charSet;
    for(int i=0; i<t.size(); i++){
        charSet[t[i]] = 1;
        charNum[t[i]]++;
    }

    int p1 = 0;
    int p2 = 0;
    int minLen = 2147483647;
    int minStart;
    int count = t.size();
    while(p1 < s.size()){
        if(count > 0){
            if(p2 == s.size())
                break;

            char chr = s[p2];
            if(charSet[chr]){
                charNum[chr]--;
                if(charNum[chr] >= 0)
                    count--;
            }
            p2++;
        }else{
            int len = p2 - p1;
            if(len < minLen){
                minLen = len;
                minStart = p1;
            }
            char chr = s[p1];
            if(charSet[chr]){
                charNum[chr]++;
                if(charNum[chr] > 0)
                    count++;
            }
            p1++;
        }
    }

    if(minLen == 2147483647)
        return "";
    else
        return s.substr(minStart, minLen);
}

总结

这一类的双指针问题主要是利用两个指针构造一个窗口，然后对窗口的内容进行讨论。

评论