这是执行此操作的递归方法:
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 时中断。下一个递归调用是这样的:
设置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] 并按顺序查找匹配项。