Java 如何确定数组是否包含单独数组中的所有整数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/21466924/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How do I determine if an array contains all the integers in a separate array
提问by BenDeV
I'm in my schools ap computer science class and I'm stuck on this one problem. and cant really even really come up with an idea on how to solve it.
我在我的学校 ap 计算机科学课上，我被这个问题困住了。并且无法真正想出如何解决它的想法。
Here it is word for word:
Write a static method named containsthat accepts two arrays of integers a1 and a2 as parameters and that returns a boolean value indicating whether or not a2's sequence of elements appears in a1 (true for yes, false for no). The sequence of elements in a2 may appear anywhere in a1 but must appear consecutively and in the same order. For example, if variables called list1 and list2 store the following values:
这是逐字逐句的：编写一个名为的静态方法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};
Then the call of contains(list1, list2)should return true because list2's sequence of values {1, 2, 1}is contained in list1 starting at index 5. If list2 had stored the values {2, 1, 2}, the call of contains(list1, list2)would return false because list1 does not contain that sequence of values. Any two lists with identical elements are considered to contain each other, so a call such as contains(list1, list1)should return true.
然后调用contains(list1, list2)应该返回真，因为 list2 的值序列{1, 2, 1}包含在 list1 中，从索引 5 开始。如果 list2 存储了值{2, 1, 2}，则调用contains(list1, list2)将返回 false，因为 list1 不包含该值序列。任何具有相同元素的两个列表都被认为是相互包含的，因此诸如此类的调用contains(list1, list1)应该返回 true。
You may assume that both arrays passed to your method will have lengths of at least 1. You may not use any Strings to help you solve this problem, nor methods that produce Strings such as Arrays.toString.
您可能假设传递给您的方法的两个数组的长度都至少为 1。您不能使用任何字符串来帮助您解决这个问题，也不能使用产生字符串的方法，例如 Arrays.toString。
If someone could point me in the right direction that would be great.
如果有人能指出我正确的方向，那就太好了。
also here's one attempt i came up with but it doesn't have a sufficient number of tests
这也是我想出的一种尝试，但它没有足够数量的测试
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;
}
回答by abiessu
Start with int first=list2[0];then find that number in list1. Next, loop over all values in list2and simultaneously loop through list1from the previously-found position until either the entire list2is verified present in list1or a discrepancy is found. Restart with firstafter the previously-found location if a discrepancy is found.
开始，int first=list2[0];然后在 中找到该数字list1。接下来，循环遍历所有值list2并同时list1从先前找到的位置循环，直到list2验证整个位置存在list1或发现差异。first如果发现差异，则在先前找到的位置之后重新启动。
Shamelessly copying another answer with a tweak:
通过调整无耻地复制另一个答案：
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;
}
This consecutive-version mechanism also ensures that no overruns occur without any extra checks.
这种连续版本机制还确保在没有任何额外检查的情况下不会发生溢出。
回答by Peter Lawrey
For consecutive
对于连续
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;
}
To avoid a label you can use a method which might be clearer
为了避免标签，您可以使用一种可能更清晰的方法
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;
}
If it only needs to be in order
如果它只需要有序
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;
}
回答by Rogue
I would say that as far as the mentality, you should think "work the first element against the array until a match".
我会说，就心态而言，您应该考虑“对数组处理第一个元素直到匹配”。
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;
In this sense, you will only advance as far down your second array for comparison as needed. If, after going through all the elements in set2, you end up with the same length, then it's contained within set1. And of course, ask if you have questions :)
从这个意义上说，您只会根据需要将第二个数组向下推进以进行比较。如果在遍历 中的所有元素set2后得到相同的长度，则它包含在set1. 当然，如果您有问题，请询问:)
回答by crush
Demo of this answer at IDEOne.com
I came up with the following function. Read the comments to understand the logic behind it:
我想出了以下功能。阅读评论以了解其背后的逻辑：
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.
}
回答by Joel
Here's a recursive way to do this:
这是执行此操作的递归方法：
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);
}
}
Each time we fail to find the matching sequence, we create a subset of the array, excluding the first element, and pass that back to contains to continue the checks.Here is an output of each iteration:
每次找不到匹配序列时，我们都会创建数组的一个子集，不包括第一个元素，并将其传回 contains 以继续检查。这是每次迭代的输出：
First time: set1 = [1, 6, 2, 1, 4, 1, 2, 1, 8] and set2 = [1, 2, 1] No match is found at the beginning of the array (we break out when comparing 6 and 2. The next recursive call is this:
第一次：set1 = [1, 6, 2, 1, 4, 1, 2, 1, 8] and set2 = [1, 2, 1] 数组开头没有找到匹配（我们比较时打断6 和 2. 下一个递归调用是这样的：
set1= [6, 2, 1, 4, 1, 2, 1, 8], [1, 2, 1]
set1= [6, 2, 1, 4, 1, 2, 1, 8], [1, 2, 1]
the next recursion compares [2, 1, 4, 1, 2, 1, 8] [1, 2, 1]
下一个递归比较 [2, 1, 4, 1, 2, 1, 8] [1, 2, 1]
and so on until the final recursion compares: [1, 2, 1, 8] [1, 2, 1] and finds the match in order.
依此类推，直到最后的递归比较： [1, 2, 1, 8] [1, 2, 1] 并按顺序找到匹配项。
回答by TwoThe
I thought about it and came up with this solution:
我想了想，想出了这个解决方案：
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
}
I call it the Lawrey-Solution.
我称之为劳瑞解决方案。
