如何确定一个数组是否包含另一个数组中的所有整数

Question

我在学校的AP计算机科学课上遇到了一个问题，我陷入了困境，甚至不能想出解决它的想法。

以下是原题：

编写一个静态方法名为contains，接受两个整数数组a1和a2作为参数，并返回一个布尔值，指示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;
}

- BenDeV

---

在第一个循环中，要注意越界的情况，即 i < set1.length - set2.length，因为你将 set1[i+1] 进行匹配，如果 i 是最后的索引，那么程序将会崩溃。否则，你基本上已经走在正确的轨道上了。 - mike

你需要一个循环，其中你要尝试将一个数组与另一个数组进行比较。当你找到匹配项时，你会寻找下一个值。如果你到达第二个数组的末尾，那么你就有了一个匹配项；如果你到达第一个数组的末尾，那么你就失败了。 - Peter Lawrey

Answer 1

连续的情况下

public static boolean contains(int[] set1, int[] set2) {
     OUTER:
     for (int i = 0; i < set1.length - set2.length; i++) {
         for (int j = 0; j < set2.length; j++) {
             if (set1[i + j] != set2[j])
                  continue OUTER;
         }
         return true;
     } 
     return false;
}

为避免使用标签，您可以使用一种可能更清晰的方法。

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

public static boolean matches(int[] set1, int off, int[] set2) {
     for (int j = 0; j < set2.length; j++)
         if (set1[off + j] != set2[j])
               return false;
     return true;
}

如果只需要按顺序排列

public static boolean contains(int[] set1, int[] set2) {
     for (int i = 0, j = 0; i < set1.length; i++)
         if (set1[i] == set2[j]) 
             if (++j >= set2.length)
                 return true;
     return false;
}

- Peter Lawrey

---

一个不错的标签使用案例哈。 - crush

@TwoThe 你甚至可以展示给我们看如何在没有标签的情况下完成这个任务。 - Peter Lawrey

@TwoThe：这有点儿傲慢...仅仅因为99.999999...%的代码是不必要的且存在缺陷... - abiessu

顺便说一句，我觉得有趣的是目前排名最高的答案有一个解决方案，在语言层面上不被认为是可以接受的（跳跃），还有两个不起作用的解决方案。 - TwoThe

就像这样简单：它在所有情况下都返回false。 - TwoThe

Answer 2

这是一种递归的方法来完成这个任务：

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时我们退出）。下一个递归调用如下：

set1= [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] 并按顺序找到匹配项。

- Joel

---

非常感谢，使用while循环比尝试测试单个值更有意义。 - BenDeV

虽然这是一个有趣的解决方案，但存在很多不必要的内存复制。 - TwoThe

@TwoThe 这里有很多内存复制，对于大数据集肯定会造成问题。在 C++ 中，我可能会使用指针算术或可选输入变量来进行偏移，或者在函数内部使用静态变量。这些在 Java 中不可用，并且任务没有提到额外的变量。因此，除了创建两个函数（一个带有 2 个输入，另一个带有 3 个输入），或者在该函数内定义一个执行相同操作的类之外，如何改变以避免数组复制并仍然保持递归呢？ - Joel

除了我下面的回答之外，还有一个问题：C++中的*(pArray + index)和Java的array[index]有什么区别？ - TwoThe

在C ++中，我可以接受指针作为输入参数，然后在递归调用函数时，可以传递指向地址pArray + 1处的元素的指针，而不是复制数组。当然，使用指针会导致确定实际数组长度的额外问题，但这是一个不同的问题，我可能会使用静态函数变量来避免它。你选择的方法是非递归的，但由于有很多这样的解决方案，我想说明另一种可能性。 - Joel

Answer 3

从int first=list2[0];开始，然后在list1中找到该数字。接下来，循环遍历list2中的所有值，并同时循环遍历list1从之前找到的位置开始，直到整个list2在list1中全部验证为存在或发现差异。如果发现差异，则在之前找到的位置后重新使用first重启。

无耻地复制另一个答案并进行微调：

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

这种连续版本机制还可以确保没有任何额外的检查就不会发生溢出。

- abiessu

Answer 4

就心态而言，我会建议您思考“对数组中的第一个元素进行匹配直到找到匹配项”。

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

在这种情况下，您只需要尽可能地向下比较第二个数组。如果在遍历set2中的所有元素后，得到与set1相同的长度，则它包含在set1中。当然，如果您有问题，请随时问 :)

- Rogue

Answer 5

在IDEOne.com上查看此答案的演示

我想出了以下函数。请阅读注释以了解其背后的逻辑：

public static boolean contains(int[] a, int[] b) {
    //Loop until there aren't enough elements left in a to match b.
    for (int i = 0; i < a.length - b.length + 1; i++) {
        for (int j = 0; j < b.length; j++) {

            //If the jth element of b doesn't match
            //the corresponding element of a, then move
            //to the next step in the sequence.
            if (a[i + j] != b[j])
                break;

            //If we are at the end of the loop, return
            //true because that means we found a consecutive match.
            if (j == b.length - 1)
                return true;

        }
    }

    return false; //If we got here, there are no matches.
}

- crush

---

在内部循环中查找 1 1 1 1 1 1 1 中的 1 2 1 会导致此错误。 - abiessu

@abiessu 我只需要检查 i < a.length - b.length + 1;。 - crush

Answer 6

我想了一下，得出了这个解决方案：

static boolean contains(final int[] list1, final int[] list2) {
  final int limit = list1.length - list2.length + 1; // we do not need to check an index >= limit, because list2 wouldn't fit anymore at this point

  for (int indexL1 = 0, indexL2 = 0; indexL1 < limit; ++indexL1) {
    while (list1[indexL1 + indexL2] == list2[indexL2]) { // check all matches from here
      ++indexL2;
      if (indexL2 == list2.length) { // if all of list2 matched so far, we found it
        return true;
      }
    }
    indexL2 = 0; // we did not find it, start from beginning of list2 again
  }

  return false; // no match found
}

我称其为Lawrey解决方案。

- TwoThe

---

+1 对于一个答案。你确定这是最简单的解决方案吗？ - Peter Lawrey

所有这些复杂性真的比不使用标签更好吗？ - Peter Lawrey

一个for循环和一个while循环，不确定是否过于复杂。如果这是最简单/最快的方法，我不知道，但它可以在没有标签、内存复制或其他花哨的东西的情况下工作。 - TwoThe