java - 查找数组中连续的匹配元素

Question

我对这个问题有一个小问题。所有的答案都会检查所有的调用，除了一个我没有得到的调用。

contains({1, 2, 1, 2, 3}, {1, 2, 3}) 本应为 true 却返回 false。

提示:

编写一个名为 contains 的静态方法，该方法接受两个整数数组 a1 和 a2 作为参数，并返回一个 boolean 值，指示是否 a2 code> 的元素序列出现在 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} 包含在从索引 5 开始的 list1 中。如果 list2 已存储这些值{2, 1, 2}，调用 contains(list1, list2) 将返回 false，因为 list1 不包含该值序列。任何两个具有相同元素的列表都被视为相互包含，因此诸如 contains(list1, list1) 之类的调用应返回 true。

您可能会假设传递给您的方法的两个数组的长度都至少为 1。您不能使用任何字符串来帮助您解决此问题，也不能使用生成字符串的方法(例如 Arrays.toString)。

代码:

public static boolean contains(int[] first, int[] second) {
    int secondCount = 0; // Indicates where to start on second array

    if (first.length < second.length) { // If second array is longer than first
        return false;
    }

    for (int i=0; i<first.length; i++) { // goes through each element in first array
        if (first[i] == second[secondCount]) { // If elements match 
            secondCount++; // increment by one and move onto next elem on second
            if (secondCount == second.length) { // If complete match
                return true;
            }
        } else { // resets count
            secondCount = 0;
        }
    }
    return false;
}

Answer 1

您的方法返回 false由于您构建循环的方式。下面，我概述了您的方法的运行时。

i = 0; secondCount = 0;
{1, 2, 1, 2, 3} {1, 2, 3}
 ^               ^
 1 == 1 ? true

i = 1; secondCount = 1;
{1, 2, 1, 2, 3} {1, 2, 3}
    ^               ^
 2 == 2 ? true

i = 2; secondCount = 2;
{1, 2, 1, 2, 3} {1, 2, 3}
       ^               ^
 1 == 3 ? false

i = 3; secondCount = 0;
{1, 2, 1, 2, 3} {1, 2, 3}
          ^      ^
 2 == 1 ? false

i = 3; secondCount = 0;
{1, 2, 1, 2, 3} {1, 2, 3}
             ^   ^
 3 == 1 ? false

return false;

问题是，如果 boolean 方程first[i] == second[secondCount]为假，则secondCount i 时重置仍然先进。因此，contains({1, 2, 1, 2, 3}, {1, 2, 3});将始终返回 false .

考虑添加 continue每当first[i] == second[secondCount]时到您的代码未能阻止i前进。