我被要求进行HackerBank代码测试，我被要求的练习是最大公共数组切片。问题如下：
给你一个n个整数的序列a0，a1，−1和任务是找到数组中不再包含的最大切片比两个不同的数字。
输入1:
[1,1,1,2,2,2,1,2,2,6,2,8]
结果1：答案是10，因为（0，9）的数组切片是数组中最大的切片，不超过两个不同的数字。
- 此切片中有10个项目，分别为"1，1，1、2、2、1、1、2和2"
- 该切片的2个不同数字是1和2
输入2:
[53800，0，0，356，8988，1，1]
结果2：答案是4，因为（1，4）的切片是最大的切片不超过两个不同数字的数组的。切片（2，5）也将是有效的，并且仍将给出4的结果。
- 此切片中有4个项目，分别为"800,0,0"
- 该切片的2个不同数字是800和0
包含不超过Java中的两个不同数字实现采用逗号分隔STDIN中的数字数组，输出被写回控制台。
我提供的实现（下面）是有效的，但是HR中有3个测试用例超时。很明显，HR隐藏了测试用例，所以我无法准确地看到触发超时的条件，甚至无法看到超时的长度。不过，考虑到我的解决方案的渐进复杂性，我对超时并不感到惊讶。但我的问题是：如何改进我的解决方案？
提前感谢所有将提供帮助的人！
import java.io.*;
import java.lang.*;
import java.util.*;
import java.util.stream.*;
public class Solution {
public static void main(String args[] ) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
List<Integer> inputSequence = parseIntegerSequence(line);
int largestSliceSize = calculateLargestSlice(inputSequence);
System.out.println(largestSliceSize);
}
private static List<Integer> parseIntegerSequence(String input) {
if (input == null)
return new ArrayList();
return Arrays.asList(input.split("\s*,\s*"))
.stream()
.filter(item -> item.matches("^\s*-?[0-9]+\s*$"))
.map(item -> Integer.parseInt(item))
.collect(Collectors.toList());
}
private static int calculateLargestSlice(List<Integer> inputSequence) {
Map<Integer, Integer> temporaryMap = new HashMap<>();
int result = 0;
int startIndex = 0;
int uniqueItemCount = 0;
Integer[] array = inputSequence.toArray(new Integer[inputSequence.size()]);
while (startIndex < array.length) { // loop over the entire input sequence
temporaryMap.put(array[startIndex], startIndex);
uniqueItemCount++;
for (int j = startIndex + 1; j < array.length; j++) {
if (temporaryMap.get(array[j]) == null) {
if (uniqueItemCount != 2) {
temporaryMap.put(array[j], j);
uniqueItemCount++;
if (j == array.length - 1) {
result = Math.max(result, j - startIndex + 1);
startIndex = array.length;
break;
}
} else {
result = Math.max(result, j - startIndex);
int item = array[j-1];
int firstFoundIndex = 0;
for( int k=j-1; k>=0; k-- )
{
if( array[k] != item )
{
firstFoundIndex = k+1;
break;
}
}
startIndex = firstFoundIndex;
temporaryMap.clear();
uniqueItemCount = 0;
break;
}
} else if (temporaryMap.get(array[j]) != null) {
if (j == array.length - 1) {
result = Math.max(result, j - startIndex + 1);
startIndex = array.length;
break;
}
}
}
}
return result;
}
}
这是我在Java中的答案，它通过了所有的HackerBank测试用例。如果您发现问题，请随时发表评论。
public static int maxCommonArraySlice(List<Integer> inputSequence) {
if(inputSequence.size() < 2) return inputSequence.size(); // I'm doubting this line should be <= 2
List<Integer> twoInts = new LinkedList<>();
twoInts.add(inputSequence.get(0));
int start = 0;
int end = inputSequence.size();
int count = 0;
int max_length = 0;
while(start < end) {
if(twoInts.contains(inputSequence.get(start))) {
count++;
start++;
}
else if(twoInts.size() == 1) {
twoInts.add(inputSequence.get(start));
}
else { // twoInts.size() is 2
count = 0;
start--;
twoInts.set(0, inputSequence.get(start));
twoInts.set(1, inputSequence.get(start + 1));
}
if(count > max_length) {
max_length = count;
}
}
return max_length;
}
public static void main(String[] args) {
List<Integer> input = new LinkedList<Integer>(Arrays.asList(53,800,0,0,0,356,8988,1,1));
System.out.println(maxCommonArraySlice(input));
}
我认为这会起作用：
public int solution(int[] arr) {
int lastSeen = -1;
int secondLastSeen = -1;
int lbs = 0;
int tempCount = 0;
int lastSeenNumberRepeatedCount = 0;
for (int current : arr) {
if (current == lastSeen || current == secondLastSeen) {
tempCount ++;
} else {
// if the current number is not in our read list it means new series has started, tempCounter value in this case will be
// how many times lastSeen number repeated before this new number encountered + 1 for current number.
tempCount = lastSeenNumberRepeatedCount + 1;
}
if (current == lastSeen) {
lastSeenNumberRepeatedCount++;
} else {
lastSeenNumberRepeatedCount = 1;
secondLastSeen = lastSeen;
lastSeen = current;
}
lbs = Math.max(tempCount, lbs);
}
return lbs;
}
参考
根据OP 的要求，这是一个python解决方案
def solution(arr):
if (len(arr) <= 2): print arr
lres = 0
rres = 0
l = 0
r = 1
last = arr[1]
prev = arr[0]
while(r <= len(arr)-1):
if prev != last:
if arr[r] == prev:
prev = last
last = arr[r]
elif arr[r] != last:
l = r-1
while(arr[l-1] == last):
l -= 1
last = arr[r]
prev = arr[r-1]
else:
if arr[r] != prev:
last = arr[r]
if r - l > rres-lres:
rres = r
lres = l
r += 1
print arr[lres:rres+1]
对于当前段，假设last是最后添加的值，prev是段中的第二个不同值。（最初它们可能是相等的）。
让我们保留指向当前段的左端和右端的指针l和r，其中最多有两个不同的元素。假设我们考虑元素arr[r]。如果当前段[l,r-1]只包含一个不同的元素，我们可以安全地添加arr[r]，并可能更新last和prev。现在，如果arr[r]等于last，那么我们不需要做任何事情。如果arr[r]等于prev，我们需要交换prev和last。如果它不等于这两个，我们需要更新l左指针，从r-1追溯到找到一个不等于last的元素，然后更新last和prev。