问题：
给定 N 个整数 A1, A2, ...。AN，德克斯特想知道他有多少种方法可以选择三个数字，使得它们是算术级数的三个连续项。
这是我的解决方案（让“频率”成为计数器）
1. Create a data store (array of sorted sets) to hold a sorted set of positions of number i in stream at index i in array.
2. for k: 0 to array.length
a. get Sorted Set S[k]
b. if SZ >=3, where SZ = S[k].size, compute SZ choose 3 and add it to freq
c. for r: 2*k-1 to k
for x in S[k]
find entries in S[r], say A, more than x and entries in S[r-i], say B, less than x.. freq += A*B
find entries in S[r], say A, less than x and entries in S[r-i], say B, more than x.. freq += A*B
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;
/**
*
* @author abhishek87
*/
class APTripletInStream {
public static void main(String[] args) {
int idx=0, numInStream;
Scanner scanIn = new Scanner(System.in), readLine;
String line = scanIn.nextLine();
readLine = new Scanner(line);
DataStore dStore = new DataStore(30000 + 1);
while(scanIn.hasNextLine()) {
line = scanIn.nextLine();
readLine = new Scanner(line);
while(readLine.hasNextInt()){
numInStream = readLine.nextInt();
dStore.add(++idx, numInStream);
}
break;
}
Long res = 0L;
try {
res = APProblemSolver.solveProblem(dStore);
} catch(Exception ex) {
res = 0L;
}
System.out.println(res);
}
}
class APProblemSolver {
public static Long solveProblem(DataStore dStore) {
Long freq = 0L;
int dSize = dStore.size();
for(int idx=1; idx<=dSize-1; idx++) {
Set currSet = dStore.getSetAtIndex(idx);
if(null != currSet && !currSet.isEmpty()) {
int size = currSet.size();
if(size >= 3) {
freq += (size*(long)(size-1)*(long)(size - 2)/6L);
}
for(int right = 2*idx-1; right > idx; right--){
if(right >= dSize)
continue;
Set rightSet = dStore.getSetAtIndex(right);
Set leftSet = dStore.getSetAtIndex(2*idx - right);
if(null != rightSet && null != leftSet) {
for(Object obj : currSet) {
Set leftSetHeadSet = ((TreeSet)leftSet).headSet(obj);
Set rightSetTailSet = ((TreeSet)rightSet).tailSet(obj);
freq += leftSetHeadSet.size() * rightSetTailSet.size();
Set leftSetTailSet = ((TreeSet)leftSet).tailSet(obj);
Set rightSetHeadSet = ((TreeSet)rightSet).headSet(obj);
freq += leftSetTailSet.size() * rightSetHeadSet.size();
}
}
}
}
}
return freq;
}
}
class DataStore {
private TreeSet[] list = null;
private int size;
public DataStore(int size) {
this.size = size;
list = new TreeSet[size];
}
public void add(Integer idx, Integer val) {
Set<Integer> i = list[val];
if(null == i) {
i = new TreeSet<Integer>();
i.add(idx);
list[val] = (TreeSet<Integer>)i;
} else{
((TreeSet<Integer>)list[val]).add(idx);
}
}
public int size() {
return size;
}
public Set getSetAtIndex(int idx) {
return list[idx];
}
}
这是我正在寻找的：
当我提交问题时，我得到“超出时间限制”。因此，我想使用 NetBeans Profiler 来估计此解决方案所需的时间，以便我可以改进它。仅供参考 - 成功提交的时间限制为 3 秒
谁能给我一些改进我的解决方案的建议[我不想改变我的解决方案]：
- 优化存储
- 我的解决方案的哪些部分很耗时并且有明显的解决方法
例子：
输入：
Number Of entries - 10.
Number Stream - 3 5 3 6 3 4 10 4 5 2.
输出：
9.
解释：
The followings are all 9 ways to choose a triplet:
(Ai, Aj, Ak) = (3, 3, 3)
(Ai, Aj, Ak) = (3, 4, 5)
(Ai, Aj, Ak) = (3, 4, 5)
(Ai, Aj, Ak) = (3, 4, 5)
(Ai, Aj, Ak) = (3, 4, 5)
(Ai, Aj, Ak) = (6, 4, 2)
(Ai, Aj, Ak) = (6, 4, 2)
(Ai, Aj, Ak) = (3, 4, 5)
(Ai, Aj, Ak) = (3, 4, 5)