大厂笔试攻略（C++/Java/Python）双指针（一）

从三个方面（后面会更新剩下的两个部分）给大家分享一下笔试中双指针考察的一些范围（有些题型面试题也喜欢考），因此建议大家对照着这些题型，学习一下~
双指针算法讲解

基础算法之一，也是笔试中比较常考的一个算法，双指针题型以及变型有很多，这里面主要列举两大类，一类是在两个数组中使用两个指针分别指向这两个数组，这一类问题中，最经典的就是判断子序列的问题，另一类则是在一个数组中使用两个指针指向这一个数组，这类问题又称为同向双指针问题，也称为滑动窗口问题，这类问题的本质其实可以理解为动态规划，比如l和r两个双指针，很多问题其实就变为以r结尾的最大值/最小值，这类问题是需要满足单调性的：当[l,r]区间不满足条件时，l指针需要左移，直到[l,r]区间满足条件为止，且当l=r时，都可以满足条件，很多时候，如果数组的数值可以取负数，是不能使用双指针来求最优解的，就是因为不满足单调性，这种题目其实比较难的是一种抽象问题的能力，有的题目需要把问题做一个转化，首先需要判断是否满足单调性，如果满足，就需要把问题转化为一个可以使用双指针去解决的一个滑动窗口问题。

题型一 多指针滑动窗口

这类题型一般是有多个数组或者字符串，然后多个指针指向不同的数组或者字符串，这类题型最经典的问题就是判断子序列问题，很多题目都可以抽象成这样一个问题。
LeetCode 392.判断子序列

题解：本题是一个多指针题型的一个模板题，可以使用两个指针分别指向字符串s和t的起始位置，如果当前位置有s[l]=t[r]，则l++，r++，如果不相等，则r++，如果最终l指向字符串s的末尾位置，则说明字符串s是t的子序列。
复杂度分析
时间复杂度：O(n+m)
空间复杂度：O(1)
C++

1.     bool isSubsequence(string s, string t) {
2.         int l=0,r=0;
3.         int n=s.size(),m=t.size();
4.         while(l<n&&r<m)
5.         {
6.             if(s[l]==t[r]){
7.                 l++;
8.             }
9.             r++;
10.         }
11.         return l==n;
12.     }

复制代码

Java

1. public boolean isSubsequence(String s, String t) {
2.     int l = 0, r = 0;
3.     int n = s.length(), m = t.length();
4.     while (l < n && r < m) {
5.         if (s.charAt(l) == t.charAt(r)) {
6.             l++;
7.         }
8.         r++;
9.     }
10.     return l == n;
11. }

复制代码

Python

1. def isSubsequence(s, t):
2.     l, r = 0, 0
3.     n, m = len(s), len(t)
4.     while l < n and r < m:
5.         if s[l] == t[r]:
6.             l += 1
7.         r += 1
8.     return l == n

复制代码

LeetCode 2410. 运动员和训练师的最大匹配数

题解：排序+双指针，对于一个运动员player来说，他应该尽可能匹配比他的数值大，且尽可能接近他的训练师trainers，如果匹配的trainers过大，会导致其他运动员可能无法匹配，因此我们可以直接把这两个数组排序，然后使用双指针模拟即可，和上面一道判断子序列的模板题的代码基本上一模一样，就是多了一个排序的代码。
复杂度分析
时间复杂度：O(nlogn)
空间复杂度：O(1)
C++

1. class Solution {
2. public:
3.     int matchPlayersAndTrainers(vector<int>& players, vector<int>& trainers) {
4.         sort(players.begin(),players.end());
5.         sort(trainers.begin(),trainers.end());
6.         int n=players.size(),m=trainers.size();
7.         int l=0,r=0;
8.         int res=0;
9.         while(l<n&&r<m){
10.             if(players[l]<=trainers[r]){
11.                 l++;
12.                 res++;
13.             }
14.             r++;
15.         }
16.         return res;
17.     }
18. };

复制代码

Java

1. class Solution {
2.     public int matchPlayersAndTrainers(int[] players, int[] trainers) {
3.         Arrays.sort(players);
4.         Arrays.sort(trainers);
5.         int n = players.length;
6.         int m = trainers.length;
7.         int l = 0, r = 0;
8.         int res = 0;
9.         while (l < n && r < m) {
10.             if (players[l] <= trainers[r]) {
11.                 l++;
12.                 res++;
13.             }
14.             r++;
15.         }
16.         return res;
17.     }
18. }

复制代码

Python

1. class Solution:
2.     def matchPlayersAndTrainers(self, players, trainers):
3.         players.sort()
4.         trainers.sort()
5.         n = len(players)
6.         m = len(trainers)
7.         l = 0
8.         r = 0
9.         res = 0
10.         while l < n and r < m:
11.             if players[l] <= trainers[r]:
12.                 l += 1
13.                 res += 1
14.             r += 1
15.         return res

复制代码

2023米哈游-子序列

题解：提供一个比较容易想到的解法：使用LeetCode 392题的思想，首先去把字符串s和t的公共部分给去除掉，然后使用两个栈去存字符串s和t的剩余部分s1和s2，对于二者的剩余部分，要么为空，要么是&#34;mhy&#34;的子串构成的字符串，否则，则不满足条件，因此，只需要把LeetCode 392题的代码做些许调整，即可ac。
大家也可以学习一下塔子哥的做法，个人感觉比较巧妙，由于部分朋友没有购买网站的会员，所以我就截图贴一下塔子哥的文字题解~
复杂度分析
时间复杂度：O(n+m)
空间复杂度：O(n+m)


塔子哥代码

1. #include <bits/stdc++.h>
3. using namespace std;
5. int bin_s[3], bin_t[3];
7. int main() {
8.         int T;
9.         cin >> T;
10.         while(T--) {
11.                 bin_s[0] = bin_s[1] = bin_s[2] = 0;
12.                 bin_t[0] = bin_t[1] = bin_t[2] = 0;
13.                 string s, t;
14.                 cin >> s >> t;
15.                 string new_s, new_t;
16.                 for(int i = 0; i < (int) s.length(); i++) {
17.                         if(s[i] == 'm') bin_s[0]++;
18.                         else if(s[i] == 'h') bin_s[1]++;
19.                         else if(s[i] == 'y') bin_s[2]++;
20.                         else new_s.push_back(s[i]);
21.                 }
22.                 for(int i = 0; i < (int) t.length(); i++) {
23.                         if(t[i] == 'm') bin_t[0]++;
24.                         else if(t[i] == 'h') bin_t[1]++;
25.                         else if(t[i] == 'y') bin_t[2]++;
26.                         else new_t.push_back(t[i]);
27.                 }
28.                 if(new_s == new_t) {
29.                         if(bin_s[0] - bin_t[0] == bin_s[1] - bin_t[1]
30.                         && bin_s[0] - bin_t[0] == bin_s[2] - bin_t[2])
31.                                 cout << &#34;Yes&#34; << endl;
32.                         else cout << &#34;No&#34; << endl;
33.                 }
34.                 else cout << &#34;No&#34; << endl;
35.         }
36.         return 0;
37. }

复制代码

C++

1. #include <bits/stdc++.h>
2. using namespace std;
3. string s,t;
4. int T;
5. bool check(string &s){
6.     int n=s.size();
7.     if(n%3){
8.         return false;
9.     }
10.     for(int i=0;i<n-3;i++){
11.         if(s.substr(i,3)!=&#34;mhy&#34;){
12.             return false;
13.         }
14.     }
15.     return true;
16. }
17. void solve(){
18.     cin>>s>>t;
19.     int n=s.size(),m=t.size();
20.     string s1,s2;
21.     int l=0,r=0;
22.     while(l<n){
23.         if(s[l]==t[r]){
24.             l++;
25.             r++;
26.             continue;
27.         }
28.         else{
29.             s1.push_back(s[l++]);
30.         }
31.     }
32.     s2=t.substr(r);
33.     if(!s2.size()){
34.         if(check(s1)){
35.             puts(&#34;Yes&#34;);
36.         }
37.         else{
38.             puts(&#34;No&#34;);
39.         }
40.     }
41.     else{
42.         if(check(s1)){
43.             puts(&#34;Yes&#34;);
44.         }
45.         else{
46.             puts(&#34;No&#34;);
47.         }
48.     }
49. }
50. int main(){
51.     cin>>T;
52.     while(T--){
53.         solve();
54.     }
55.     return 0;
56. }

复制代码

Java

1. import java.util.Scanner;
3. public class Main {
4.     public static void main(String[] args) {
5.         Scanner scanner = new Scanner(System.in);
6.         int T = scanner.nextInt();
7.         scanner.nextLine(); // Consume the newline character
8.         
9.         while (T-- > 0) {
10.             String s = scanner.nextLine();
11.             String t = scanner.nextLine();
12.             int n = s.length();
13.             int m = t.length();
14.             String s1 = &#34;&#34;;
15.             String s2 = &#34;&#34;;
16.             int l = 0, r = 0;
18.             while (l < n) {
19.                 if (s.charAt(l) == t.charAt(r)) {
20.                     l++;
21.                     r++;
22.                 } else {
23.                     s1 += s.charAt(l++);
24.                 }
25.             }
27.             s2 = t.substring(r);
29.             if (s2.isEmpty()) {
30.                 if (check(s1)) {
31.                     System.out.println(&#34;Yes&#34;);
32.                 } else {
33.                     System.out.println(&#34;No&#34;);
34.                 }
35.             } else {
36.                 if (check(s1)) {
37.                     System.out.println(&#34;Yes&#34;);
38.                 } else {
39.                     System.out.println(&#34;No&#34;);
40.                 }
41.             }
42.         }
43.     }
45.     private static boolean check(String s) {
46.         int n = s.length();
47.         if (n % 3 != 0) {
48.             return false;
49.         }
50.         for (int i = 0; i < n - 3; i++) {
51.             if (!s.substring(i, i + 3).equals(&#34;mhy&#34;)) {
52.                 return false;
53.             }
54.         }
55.         return true;
56.     }
57. }

复制代码

Python

1. def check(s):
2.     n = len(s)
3.     if n % 3:
4.         return False
5.     for i in range(n - 2):
6.         if s[i:i + 3] != &#34;mhy&#34;:
7.             return False
8.     return True
10. def solve():
11.     s = input()
12.     t = input()
13.     n = len(s)
14.     m = len(t)
15.     s1 = &#34;&#34;
16.     s2 = &#34;&#34;
17.     l = 0
18.     r = 0
20.     while l < n:
21.         if s[l] == t[r]:
22.             l += 1
23.             r += 1
24.         else:
25.             s1 += s[l]
26.             l += 1
28.     s2 = t[r:]
30.     if not s2:
31.         if check(s1):
32.             print(&#34;Yes&#34;)
33.         else:
34.             print(&#34;No&#34;)
35.     else:
36.         if check(s1):
37.             print(&#34;Yes&#34;)
38.         else:
39.             print(&#34;No&#34;)
41. T = int(input())
42. for _ in range(T):
43.     solve()

复制代码

有关面试算法题题解在我的知乎专栏：面试算法题题解 - 知乎 (zhihu.com)
有关笔试真题解析的文章在我的知乎专栏：笔试真题解析 - 知乎 (zhihu.com)
有关大厂笔试的常考算法题在我知乎的置顶文章笔试刷题指南中有相关的练习题：笔试刷题指南
笔试ACM输入以及常见考点和技巧在我的知乎专栏：笔试攻略 - 知乎 (zhihu.com)