我想解决这个 CodeChef挑战：
假设我们给定了一个由N（范围为100,000个）元素组成的数组A。我们将找到3个这样的元素1 <= Ai，Aj，Ak <= 30,000的所有对的计数，
Aj-Ai = Ak- Aj and i < j < k
换句话说，Ai，Aj，Ak处于算术级数。例如Array：
9 4 2 3 6 10 3 3 10
因此，AP是：
{2,6,10},{9,6,3},{9,6,3},{3,3,3},{2,6,10}
所以要求的答案是5。
我尝试的是以30,000个长数组命名为过去和右边。最初的right包含每个1-30,000元素的计数。
如果我们在第i个位置，则过去将在i之前存储数组值的计数，而右边将在i之后存储数组值的计数。我只是循环查找数组中所有可能的共同差异。这是代码：
right[arr[1]]--; for(i=2;i<=n-1;i++) { past[arr[i-1]]++; right[arr[i]]--; k=30000 - arr[i]; if(arr[i] <= 15000) k=arr[i]; for(d=1;d<=k;d++) { ans+= right[arr[i] + d]*past[arr[i]-d] + past[arr[i] + d]*right[arr[i]-d]; } ans+=past[arr[i]]*right[arr[i]]; }
但是，这使我超过了时间限制。请提供更好的算法帮助。
如果您对列表进行第一次遍历，并且仅提取可能有3项AP的数字对（差异为0 mod 2），则可以大大缩短执行时间。然后在这些对之间进行迭代。
伪C ++-y代码：
// Contains information about each beginning point struct BeginNode { int value; size_t offset; SortedList<EndNode> ends; //sorted by EndNode.value }; // Contains information about each class of end point struct 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 collection List<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;
