問題：
N 個の整数 A1、A2、… が与えられます。AN、デクスターは、算術数列の連続する 3 つの項になるように 3 つの数を選択する方法がいくつあるか知りたがっています。
これが私の解決策です（「freq」をカウンターにします）
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)