阵列中3个长度的AP的最快算法计数

如果您对列表进行第一次遍历，并且仅提取可能有3项AP的数字对（差异为0 mod 2），则可以大大缩短执行时间。然后在这些对之间进行迭代。

伪C ++-y代码：

// Contains information about each beginning pointstruct BeginNode {  int value;  size_t offset;  SortedList<EndNode> ends;  //sorted by EndNode.value};// Contains information about each class of end pointstruct EndNode {  int value;  List<size_t> offsets; // will be sorted without effort due to how we collect offsets};struct Result {  size_t begin;  size_t middle;  size_t end;};SortedList<BeginNode> nodeList;foreach (auto i : baseList) {  BeginNode begin;  node.value = i;  node.offset = i's offset; //you'll need to use old school for (i=0;etc;i++) with this  // baseList is the list between begin and end-2 (inclusive)  foreach (auto j : restList) {     // restList is the list between iterator i+2 and end (inclusive)    // we do not need to consider i+1, because not enough space for AP    if ((i-j)%2 == 0) { //if it's possible to have a 3 term AP between these two nodes      size_t listOffset = binarySearch(begin.ends);      if (listOffset is valid) {        begin.ends[listOffset].offsets.push_back(offsets);      } else {        EndNode end;        end.value = j;        end.offsets.push_back(j's offset);        begin.ends.sorted_insert(end);      }    }  }  if (begin has shit in it) {    nodeList.sorted_insert(begin);  }}// Collection done, now iterate over collectionList<Result> res;foreach (auto node : nodeList) {  foreach (auto endNode : node.ends) {    foreach (value : sublist from node.offset until endNode.offsets.last()) {      if (value == average(node.value, endNode.value)) {        // binary_search here to determine how many offsets in "endNode.offsets" "value's offset" is less than.        do this that many times:          res.push_back({node.value, value, endNode.value});      }    }  }}return res;