这是查找数组是否是另一个数组的子数组的错误方法吗？

Question

bool isSubset(int arr1[], int m,int arr2[], int n){
    set<int> hashset;
    for (int i = 0; i < m; i++){
        hashset.insert(arr1[i]);
    }
    for (int i = 0; i < n; i++) {
        if (hashset.find(arr2[i]) == hashset.end())
            return false;
    }
    return true;
}

这个判断arr2是否是arr1的子数组的方法是否正确因为子数组是数组的连续部分，但此代码不检查任何顺序，这就是我想要确定的原因。

Answer 1

Is this correct method to find whether arr2 is sub array of arr1 or not

不，不是。您的方法不考虑元素的顺序。它更像是一种查找 arr1.

中是否存在一堆数字（在 arr2 中给出）的方法

例如，如果 int arr1[] = {1, 2, 3} 和 int arr2[] = {2, 1}，您实现的方法将 return true，而它应该 return false .

以下是您的操作方式：

#include <iostream>

bool isSubset(int array[], int m, int subarray[], int n)
{
    if (n > m)
        return false;
    
    for (int i = 0; i <= m-n; i++) {
        int ii = i, j;
        for (j = 0; j < n; j++)
            if (subarray[j] != array[ii])
                break;
            else
                ii++;
        
        if (j == n)
            return true;
    }
    
    return false;
}

然后这样称呼它：

int main()
{
    int array[] = {1, 2, 3};
    const int m = sizeof(array) / sizeof(*array);
    
    int subarray1[] = {1, 2};
    const int n1 = sizeof(subarray1) / sizeof(*subarray1);

    int subarray2[] = {2, 1};
    const int n2 = sizeof(subarray2) / sizeof(*subarray2);
    
    std::cout << isSubset(array, m, subarray1, n1) << "\n"; // Will print 1
    std::cout << isSubset(array, m, subarray2, n1) << "\n"; // Will print 0
}

Answer 2

您了解您的代码检查子数组的方式是错误的。

一个建议-

不鼓励在 C++ 中使用 C 语言样式数组。相反，您应该使用 Containers library. You can use std::array 容器中提供的适当标准容器来代替普通 C 样式数组。下面是检查子数组的示例代码：

#include <iostream>
#include <array>
#include <algorithm>

int main () {
    std::array<int,12> arr1 {9,5,2,5,9,2,4,7,0,4,5,1};
    std::array<int,3> arr2 {5,9,2};
    bool res = false;    
    size_t pos = 0;
    std::array<int,12>::iterator x;

    while ((x = std::find(arr1.begin() + pos, arr1.end(), arr2[0])) != arr1.end()) {
        size_t currpos = x - arr1.begin();

        if ((arr1.size() - currpos >= arr2.size()) &&
           ((std::equal(arr1.begin() + currpos, arr1.begin() + currpos + arr2.size(), arr2.begin())))) {
            res = true;
            break;
        }

        pos = currpos + 1;
    }

    if (res) {
        std::cout << "arr2 is subarray of arr1" << std::endl;
    } else {
        std::cout << "arr2 is not subarray of arr1" << std::endl;
    }

    return 0;
}

这是查找数组是否是另一个数组的子数组的错误方法吗？

Is this a wrong approach to find whether array is subarray of another array?

c++

arrays

sub-array

data-structures