java Stumpped：在两个整数数组中检测相同的整数序列

Question

首先，我是一个java新手。我一直在寻找一种简洁的方法来解决这个问题，它不涉及列表或哈希表，但还没有找到：

**注意，这不是家庭作业，而是“构建Java程序”第7章中的练习#14

编写一个名为contains的方法，该方法接受两个整数数组作为参数，并返回一个布尔值指示第二个数组的元素是否出现在第一个数组中

例如：

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

Integer[] list2 = {1,2,1};

调用contains(list1, list2)将返回true。我得到了嵌套for循环的想法，它可以遍历数组，但我看不到明确的解决方案：

public static Boolean contains(Integer[] listOfNumbers1, Integer[] listOfNumbers2){

    for(int i = 0 ; i < listOfNumbers2.length; i++){

        for(int j = 0 ; j < listOfNumbers1.length; j++){

        }
    }

    return true;
}

Answer 1

（您实际上没有指定是否需要考虑重复项，从您的示例来看，您似乎正在尝试查看array1是否将array2的所有元素按顺序排列）

有几种不同的情况需要考虑：

1. array2 is longer than array1:
       if this is the case the result must be false because array1 can't 
       possibly have the same elements in order since array2 is longer

2. array2 is the same size as array1: 
       for this step you can use a single loop and compare the elements in order, 
       if you find a  mismatch then array1 does not contain array2

       for i from 0 to length do
           if array1[i] != array2[i]
              // false
           end
       end
       // true

3. array2 is shorter than array1:
       for this case you need to examine every array2.length elements from array1 
       and see if they match array2

       matches = 0
       for i from 0 to array1.length do
           for j from 0 to array2.length do
               if array1[i] == array2[j] 
                  // increment i
                  // increment matches
               end
           end
           if matches == array2.length
               // true
           else
               // false
           end
           matches = 0  // reset matches
       end

Answer 2

因此，基本上，我们希望遍历搜索数组（listOfNumbers1）中的每个位置，并检查它是否是我们要查找的序列的开始（listOfNumbers2）

// Loops through the search array
for( int i = 0; i < listOfNumbers1.length; i++ )
{
    boolean found = true;
    for(int j = 0; j < listOfNumbers2.length; j++ )
    {
        /* Check if the following conditions hold
           - Not going to cause an ArrayIndexOutOfBoundsException
           - Values do **not** match => set found to false */
        if( i+j < listOfNumbers1.length && listOfNumbers1[i + j] != listOfNumbers2[j] )
        {
            // Didn't find the sequence here
            found = false;
        }
    }

    // If found is still true, we have found the sequence and can exit
    if( found ) return true;
}

return false;

Answer 3

class contains{
    public static void main(String[] args){
        int[] list1 = {1,6,2,1,4,1,2,1,8};
        int[] list2 = {1,2,1};

        if(contains(list1, list2)){
            System.out.println("list2 found in list1");
        }
        else {
            System.out.println("list2 not found in list1");
        }
    }

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