测试用例无法满足

debugcn 发表于 Dev

拉加夫

我只是一个初学者。我遇到了这个问题，我的代码无法满足所有/大多数测试用例。

问题：

给定一个数字数组，请找到最小和最大元素相同的非空子数组的数量。

例子：

输入：数组= [1、1、3]

输出4

解释：

所需的子数组为[1]，[1]，[3]，[1,1]

我的解决方案：

对数组进行排序并解决问题。

代码：

for(int i = 0; i < testCases; i++){
        int arraySize = in.nextInt();
        int array[] = new int[arraySize];
        for(int j = 0; j < arraySize; j++){
            array[j] = in.nextInt();
        }
        temp[i] = (findSubArrays(array));
}
for(int i = 0; i < testCases; i++){
        System.out.println(temp[i]);
}

private static int findSubArrays(int[] array) {
    Arrays.sort(array);

   //Since each element can form a sub-array of its own
    int noOfSubArrays = array.length;

    for(int i = 0; i < array.length-1; i++){
        if(array[i] == array[i+1]){
            noOfSubArrays++;
        }
    }
    return noOfSubArrays;
}

shmosel

因此，您正在对数组进行排序，以使起点和终点保持相邻，因此您不需要嵌套的遍历。那讲得通。问题在于您要计算相邻的重复项，但真正需要的是T(n)或连续重复项的三角形数。考虑一个简单的场景：

[1, 1, 1]

您的算法返回5，但实际上有6个子集（按开始和结束索引）：

0, 0
0, 1
0, 2
1, 1
1, 2
2, 2

因此，让我们更新算法以计算每个序列的三角形数：

private static int findSubArrays(int... array) {
    Arrays.sort(array);

    int sequenceCount = 0;
    int total = 0;
    for (int i = 0; i < array.length + 1; i++) {
        if (i == array.length || (i > 0 && array[i] != array[i - 1])) {
            total += triangle(sequenceCount);
            sequenceCount = 0;
        }
        sequenceCount++;
    }
    return total;
}

private static int triangle(int n) {
    return (n * (n + 1)) / 2;
}

现在调用findSubArrays(1, 1, 1)return6和findSubArrays(1, 1, 3)return 4。

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。