可以有效存储和检查任何三个连续添加的元素的总数是否等于给定总数的数据结构

Question

例子：没有总计的空容器。添加{1,2,3}，这意味着仅存在一个总数（1 + 2 + 3 = 6）。现在添加{4}元素，它从{2，3，4}创建额外的总数。现在将有两个总数（1 + 2 + 3 = 6和2 + 3 + 4 = 9）。

Answer 1

您可以结合使用列表（以跟踪添加的元素）和从总和到元素的映射的组合：

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());

    }

}

笔记：

1. 虽然这个示例中的API很奇怪，但是它显示了该思想的基础。可以很容易地对其进行调整，以返回更适合您需求的东西。

2. 如果您需要概括实现以容纳更大系列的总和，而不仅仅是三胞胎，那么缓存“滚动窗口”总和可能是个好主意。为了使代码更简洁，我没有这样做。