如何修复数组子序列检测函数？现有实现存在匹配遗漏问题

你的核心问题是匹配失败时直接重置j为0并让i继续前进，这会跳过原数组中可能的新起始位置，比如你例子里的第二个4（索引2）就被错过了。另外代码里还有一个逻辑错误：判断匹配完成的条件写成了j == fSize - 1，这应该是j == sSize（子序列的长度）。

方案一：双重循环（逻辑清晰易维护） #

这种方法直接遍历原数组的每个可能起始位置，检查从该位置开始是否能完整匹配子序列：

#include <iostream>
using namespace std;

bool isSubArray(int firstArr[], int secondArr[], int fSize, int sSize) {
    // 边界情况处理
    if (sSize == 0) return true;
    if (sSize > fSize) return false;

    // 遍历所有可能的起始位置
    for (int i = 0; i <= fSize - sSize; ++i) {
        int matchCount = 0;
        // 检查当前起始位置是否能匹配整个子序列
        for (int j = 0; j < sSize; ++j) {
            if (firstArr[i + j] == secondArr[j]) {
                matchCount++;
            } else {
                break;
            }
        }
        // 匹配所有元素则返回true
        if (matchCount == sSize) {
            return true;
        }
    }
    // 遍历完无匹配
    return false;
}

// 测试示例
int main() {
    int arr1[6] = {1,4,4,0,4,2};
    int subarr[3] = {4,0,4};
    cout << boolalpha << isSubArray(arr1, subarr, 6, 3) << endl; // 输出true
    return 0;
}

方案二：优化双指针（避免重复遍历） #

如果你想保留双指针的思路，需要在匹配失败时回退i的位置，而不是让它继续前进。具体来说，当已经匹配了j个元素后失败，i需要回到i - j + 1的位置（当前匹配起始点的下一个位置），同时重置j为0：

#include <iostream>
using namespace std;

bool isSubArray(int firstArr[], int secondArr[], int fSize, int sSize) {
    // 边界情况处理
    if (sSize == 0) return true;
    if (sSize > fSize) return false;

    int i = 0;
    int j = 0;

    while (i < fSize && j < sSize) {
        if (firstArr[i] == secondArr[j]) {
            // 匹配成功，双指针前进
            i++;
            j++;
        } else {
            // 匹配失败，回退i到起始点下一位，重置j
            if (j != 0) {
                i = i - j + 1;
                j = 0;
            } else {
                // 未匹配过，直接前进i
                i++;
            }
        }
    }

    // j走完子序列则匹配成功
    return j == sSize;
}

// 测试示例
int main() {
    int arr1[6] = {1,4,4,0,4,2};
    int subarr[3] = {4,0,4};
    cout << boolalpha << isSubArray(arr1, subarr, 6, 3) << endl; // 输出true
    return 0;
}

关键修复点说明 #

1. 修正匹配完成的判断条件：原来的j == fSize - 1是错误的，应该判断j == sSize——当j等于子序列的长度时，说明所有元素都匹配完成。
2. 处理匹配失败的回退逻辑：在双指针方案中，当部分匹配后失败，不能直接让i继续前进，而是要回到当前匹配起始点的下一个位置，这样不会错过可能的新起始位置（比如你例子中的第二个4）。

内容的提问来源于stack exchange，提问作者Math Student