java - 如何确定一个数组是否包含单独数组中的所有整数

Question

我在学校的 ap 计算机科学课上遇到了这个问题。甚至无法真正想出解决方法。

这里是逐字逐句的: 编写一个名为 contains 的静态方法，它接受两个整数数组 a1 和 a2 作为参数，并返回一个 boolean 值，指示 a2 的元素序列是否出现在 a1 中(true 表示是，false 表示否) . a2 中的元素序列可以出现在 a1 中的任何位置，但必须以相同的顺序连续出现。例如，如果名为 list1 和 list2 的变量存储以下值:

int[] list1 = {1, 6, 2, 1, 4, 1, 2, 1, 8};
int[] list2 = {1, 2, 1};

然后 contains(list1, list2) 的调用应该返回 true 因为 list2 的值序列 {1, 2, 1} 包含在 list1 中从索引 5 开始. 如果 list2 存储了值 {2, 1, 2}，则 contains(list1, list2) 的调用将返回 false，因为 list1 不包含该值序列.任何两个具有相同元素的列表都被视为彼此包含，因此 contains(list1, list1) 等调用应返回 true。

您可能会假设传递给您的方法的两个数组的长度至少为 1。您可能不会使用任何字符串来帮助您解决此问题，也可能不会使用生成字符串的方法，例如 Arrays.toString。

如果有人能为我指出正确的方向，那就太好了。

这也是我想出的一个尝试，但它没有足够数量的测试

public static boolean contains(int[] set1, int[] set2) {
    boolean contains = false;
    for (int i = 0; i < set1.length; i++) {
        for (int a = 0; a < set2.length - 1; a++) {
            if (set1[i] == set2[a] && set1[i + 1] == set2[a + 1]) {
                contains = true;
            } else {
                contains = false;
            }
        }
    }
    return contains;
}

Answer 1

这是一个递归的方法:

public static boolean contains(int[] set1, int[] set2) {
    //System.out.println(Arrays.toString(set1) + " " + Arrays.toString(set2));

    //set 2 cannot be contained within set 1 because there aren't 
    //enough elements. This either means that we recursed too deep
    //within the first set that there are not enough elements, or
    //there were not enough elements to begin with.
    if (set1.length < set2.length) return false;

    //from the start of each set, count the number of matches in order
    int numMatched = 0;
    while (numMatched < set2.length && set1[numMatched] == set2[numMatched]) {
        numMatched++;
    }

    if (numMatched == set2.length) 
        //the number of matches found equals the length of the set to
        //search for, so we have found a match. Return true to unravel
        //the recursion.
        return true;
    else {
        //we didn't find a match, so shift the array by 1 and then
        //recursively call this function to compare again.
        int[] subset = Arrays.copyOfRange(set1,  1,  set1.length);
        return contains(subset, set2);
    }

}

每次找不到匹配序列时，我们都会创建数组的一个子集，不包括第一个元素，并将其传回包含以继续检查。这是每次迭代的输出:

第一次:set1 = [1, 6, 2, 1, 4, 1, 2, 1, 8] 和 set2 = [1, 2, 1] 在数组的开头没有找到匹配项(我们在比较6和2的时候打断了，接下来的递归调用是这样的:

设置1= [6, 2, 1, 4, 1, 2, 1, 8], [1, 2, 1]

下一个递归比较 [2, 1, 4, 1, 2, 1, 8] [1, 2, 1]

等等，直到最后的递归比较: [1, 2, 1, 8] [1, 2, 1] 并按顺序找到匹配项。