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

我在学校的计算机科学课上，我坚持这个问题。 并且甚至不能真正想出如何解决它的想法。

这是逐字逐句的：写一个名为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} 1,2,1 {1, 2, 1}包含在list1中的list1中。如果list2存储了值{2, 1, 2} 2,1,2 {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); } } 

每次我们找不到匹配的序列时，我们创建一个数组的子集，排除第一个元素，然后将其传递回contains来继续检查。这是每次迭代的输出：

第一次：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]并按顺序查找匹配。

Answer 2

连续

 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; } 

Answer 3

我会说，就心态而言，你应该认为“在匹配之前对数组起作用的第一个元素”。

 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; 

从这个意义上说，你只需要在你的第二个arrays中向前推进，以便根据需要进行比较。 如果在遍历set2所有元素后，最终得到相同的长度，则它包含在set1 。 当然，问你是否有问题:)

Answer 4

从int first=list2[0]; 然后在list1找到该数字。 接下来，循环遍历list2所有值，同时从先前找到的位置循环遍历list1 ，直到list1中的整个list2被validation，或者找到差异。 如果发现差异，请在先前找到的位置后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; } 

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

Answer 5

在IDEOne.com上演示此答案

我想出了以下function。 阅读评论以了解其背后的逻辑：

 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. } 

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-Solution。