arrays - 查找给定值的所有数组子序列

Question

我正在寻找一种给出如下列表的算法:

[1, 1, 2, 1, 1, 5, 1, 1, 1, 1, 2, 1]

可以找到并返回给定值的所有子序列。例如，如果给定值 1，函数将返回 [[1, 1], [1, 1], [1, 1, 1, 1], [1]] .

我认为这类似于求和数组的所有子序列或查找给定字符串的所有子序列之类的问题，但算法从来都不是我的强项。答案可以是伪代码或语言不可知论。如果您不介意，能否解释一下解决方案的复杂性？

如果有帮助，我可以解释我需要它做什么。如果需要，请发表评论。

Answer 1

我们可以通过扫描数组两次来在 O(n) 时间复杂度内完成此操作。伪代码:

//use an array list so we can access element at an index in O(1) time
outputArrays = new ArrayList<int[]> //list of arrays

//loop to declare arrays of outputs - this scans each element once
int currLen = 0;
for (item in inputArray) {
 if (item = itemToLookFor) {
  currLen++;
 }else if (currLen > 0) {
  currLen = 0;
  outputArrays.add(new int[currLen]);
 }
}

//loop to actually populate the output - this scans each element once
currLen = 0;
currIndex = 0;
for (item in inputArray) {
 if (item = itemToLookFor) {
  outputArrays.getElement(currIndex)[currLen] = item;
  currLen++;
 }else if (currLen > 0) {
  currLen = 0;
  currIndex++;
 }
}

如果有什么我可以澄清的，请告诉我。