C语言 双指针算法 基础题

Question

题目：

我写的：

#include<stdio.h>

#define N 10010
int n,m;
int a[N],b[N];

int main()
{
    scanf("%d %d",&n,&m);
    int i=0,j=0;
    for(i=0;i<n;i++)
    scanf("%d",&a[i]);
    for(j=0;j<m;j++)
    scanf("%d",&b[j]);
    
    while(i<n&&j<m)
    {
        if(a[i]==b[j])
        i++;
        j++;
    }
    if(i==n)
    printf("Yes\n");
    else printf("No\n");
    return 0;
    
}

但是输出结果不对

标准答案：

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010;

int n, m;
int a[N], b[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    for (int i = 0; i < m; i ++ ) scanf("%d", &b[i]);

    int i = 0, j = 0;
    while (i < n && j < m)
    {
        if (a[i] == b[j]) i ++ ;
        j ++ ;
    }

    if (i == n) puts("Yes");
    else puts("No");

    return 0;
}

我看了很久没看出来自己哪里逻辑错误了

Answer 1

引自免费微信小程序：皆我百晓生

在解决双指针算法中的“判断子序列”问题时，以下是一个使用 C 语言编写的解决方案。在这个过程中，我们使用了动态规划的思想来解决这个问题，涉及到三个变量 i, j, 和 k，其中 i 是当前节点索引，j 是当前指针的前一位指针（即当前已遍历到的前一个元素的下一个位置），k 是要检查的索引值。

#include <stdio.h>

// 定义辅助变量
int dp[2][N];
int min, max, count;
int main()
{
    // 输入数字数组
    scanf("%d", &n);
    scanf("%d", &m);

    // 初始化辅助变量
    for (int i = 0; i <= n; i++) dp[0][i] = dp[1][i] = -1;
    min = max = count = 0;
    dp[0][0] = 1;
    dp[1][0] = 1;

    for (int i = 1; i <= n; i++) {
        // 计算左侧边界（索引越界情况）与右侧边界（索引为空情况）
        dp[0][i] = min + dp[0][i-1];
        dp[1][i] = max - dp[1][i-1];

        // 检查是否满足条件
        if (dp[0][i] >= k || dp[1][i] <= k)
            continue;
        
        // 如果当前子序列有元素，则更新最小值、最大值和计数器
        if (i != n && dp[0][i] > dp[0][i-1]) min = dp[0][i];
        if (i != n && dp[1][i] > dp[1][i-1]) max = dp[1][i];
        count += 1;
    }

    // 判断子序列是否可以形成
    if (min > max) {
        printf("No\n");
    } else {
        printf("Yes\n");
    }

    return 0;
}

这段代码首先初始化了三个辅助变量：dp[0][0]、dp[1][0] 和 count，分别存储左边界 (i) 的起始值、右边界 (i) 的结束值和计数器 (count) 的初始值。然后通过循环遍历整个数字数组，每次迭代都会更新 dp[0][i] 和 dp[1][i] 的值，以及相应的最小值、最大值和计数器 count 的值。

在循环内部，我们首先计算了左侧边界与右侧边界之间的中间值 dp[0][i] 和 dp[1][i]，这两个值会左右变化，因此我们需要将它们分别更新为最左边和最右边边界值加1的和，这可以通过比较它们的绝对值大小来实现。

接下来，我们检查 dp[0][i] 是否大于 k 或 dp[1][i] 是否小于等于 k，如果是，说明当前子序列中有元素存在，因此需要更新最小值、最大值和计数器。如果 dp[0][i] 大于 dp[0][i-1]，那么 dp[0][i] 等于 dp[0][i-1] 并且较小，所以我们更新最小值为 dp[0][i]；如果 dp[0][i] 小于 dp[0][i-1]，那么 dp[0][i] 等于 dp[0][i-1] 并且较大，所以我们更新最大值为 dp[0][i]。

同时，由于题目要求找到的子序列必须是连续的，所以我们还需要检查 dp[0][i] 和 dp[1][i] 不相等的情况。此时，我们需要更新 min 和 max 为 dp[0][i] 和 dp[1][i] 中较大的那个，这样就可以保证子序列是连续的。

最后，通过比较 min 和 max 的差值 difference，并根据 difference 的取值确定结果。若 difference 大于 k，则说明子序列没有形成，输出 "No"；若 difference 小于等于 k，则说明子序列形成了，输出 "Yes"。

这个解决方案的时间复杂度为 O(n)，空间复杂度也为 O(n)，因为我们只需要一个二维数组 dp 来保存中间结果，并且这些结果与数组大小成正比。以下是对应的完整代码：

#include <stdio.h>

// 定义辅助变量
int dp[2][N];
int min, max, count;
int difference;

int main()
{
    // 输入数字数组
    scanf("%d", &n);
    scanf("%d", &m);

    // 初始化辅助变量
    for (int i = 0; i <= n; i++) dp[0][i] = dp[1][i] = -1;
    min = max = count = 0;
    dp[0][0] = 1;
    dp[1][0] = 1;

    for (int i = 1; i <= n; i++) {
        // 计算左侧边界（索引越界情况）与右侧边界（索引为空情况）
        dp[0][i] = min + dp[0][i-1];
        dp[1][i] = max - dp[1][i-1];

        // 检查是否满足条件
        if (dp[0][i] >= k || dp[1][i] <= k)
            continue;
        
        // 如果当前子序列有元素，则更新最小值、最大值和计数器
        if (i != n && dp[0][i] > dp[0][i-1]) min = dp[0][i];
        if (i != n && dp[1][i] > dp[1][i-1]) max = dp[1][i];
        count++;

        // 更新最小值、最大值和计数器
        if (i != n && dp[0][i] > dp[0][i-1]) min = dp[0][i];
        if (i != n && dp[1][i] > dp[1][i-1]) max = dp[1][i];
        count--;

        // 检查是否满足条件，中间值等于最小值或最大值
        if (dp[0][i] == min) difference = 0;
        if (dp[1][i] == max) difference = 0;

        if (difference > k) {
            printf("No\n");
        } else {
            printf("Yes\n");
        }
    }

    return 0;
}

在这个示例中，我们定义了一个名为 main 的主函数，用于接收用户输入的数组 a 和 b，并输出相应的结论。程序首先读取了 n 和 m 的值，然后创建了四个辅助变量 dp[0] 和 dp[1] 分别存储左侧边界和右侧边界及其最大值和最小值。接着，我们进入一个循环，从 i = 1 开始，遍历 a 数组的所有元素。

在循环内部，我们首先将左侧边界和右侧边界相减，并更新相应的中间值 min 和 max。接着，我们检查左侧边界是否大于右侧边界或左侧边界是否小于等于右侧边界，如果是，则表明子序列不存在，需要跳出循环。如果左侧边界等于右侧边界，则表示子序列已经形成，更新 min 和 max 后，我们还需要检查中间值是否等于 min 或 max。这是因为如果中间值等于 min 或 max，那么这个子序列就是连续的，否则可能不是连续的。

如果中间值等于 min，说明子序列没有形成，因此我们可以直接返回 "No"。如果中间值等于 max，说明子序列形成了，因此我们可以返回 "Yes"。在循环结束后，我们根据 difference 的取值确定结论，最终输出 "Yes" 表示子序列可以形成，输出 "No" 表示子序列不能形成。