例子：沒有總計的空容器。添加{1,2,3}，這意味著僅存在一個總數（1 + 2 + 3 = 6）。現在添加{4}元素，它從{2，3，4}創建額外的總數?，F在將有兩個總數（1 + 2 + 3 = 6和2 + 3 + 4 = 9）。
2 回答
慕娘9325324
TA貢獻1783條經驗 獲得超4個贊
您可以結合使用列表（以跟蹤添加的元素）和從總和到元素的映射的組合：
public class SummingList {
// Store the elements added in order
private List<Integer> elements = new ArrayList<>();
// Map form the sum to the index(es) that sum up to that number
private Map<Integer, List<Integer>> sumIndexes;
/** Expose elements from the list:
public int get(int index) {
return list.get(index);
}
/** Add an element to the data structure */
public add(int element) {
list.add(element);
// If there are now at least three elements in the data structure,
// sum them:
int size = list.size();
if (size >= 3) {
int sum = list.get(size - 3) + list.get(size - 2) + list.get(size - 1);
sumIndexes.computeIfAbsent(sum, k -> new LinkedList<>()).add(size - 3);
}
}
/**
* Returns a list of indexes in the list, where each index is the beginning
* of a series of three elements who's sum is the passed {@code sum}.
* If no such indexes exist, an empty list is returned.
*/
public List<Integer> getSequencesWIthSum(int sum) {
return Collections.unmodifiable(
sumIndexes.getOrDefault(sum, Collections.emptyList());
}
}
筆記：
雖然這個示例中的API很奇怪，但是它顯示了該思想的基礎?？梢院苋菀椎貙ζ溥M行調整，以返回更適合您需求的東西。
如果您需要概括實現以容納更大系列的總和，而不僅僅是三胞胎，那么緩存“滾動窗口”總和可能是個好主意。為了使代碼更簡潔，我沒有這樣做。
添加回答
舉報
0/150
提交
取消