首先，我们先来讨论一下预计算所有结果，然后让它们更有效地被访问。
预计算所有索引对<i, j>，其中a[i] + a[j] = sum可以在O(n)中离线执行，其中n是输入数组a的大小。
然后，您可以将预先计算的对存储在2D空间索引结构中（例如，R树或四叉树）。
然后，子数组查询(start, end)对应于2d索引上的范围查询（具有二次框），其中min = (start, start)和max = (end, end)。
根据查询的范围，这在O（log m）中应该是可能的，其中m是对的总数。

不需要为特定的总和构建哈希表：可以在初始步骤中构造散列表，并且对于整个阵列，可以在线性时间内回答对任何sum的查询。
对于长度为n的数组arr，请执行以下步骤：

• 构建一个哈希表，在其中存储arr中具有值arr[i]的元素的数量。
• 对于每个sum：从0的total开始
• 对于x = arr[i]集合arr的每个元素：
• 如果x * 2 < sum，得到值为sum - x的元素的count，将count * 2添加到total。
• 如果x * 2 == sum，则获取值为x的元素的count，将count + 1添加到total
• arr的元素对的数目加起来为sum是total / 2

要回答子数组的查询，上述方法不起作用。当然，你可以总是使用嵌套循环，并在没有额外空间的情况下找到二次时间的计数。
下面是一个针对子阵列和任何给定sum的更有效的解决方案：

• 初始步骤：构造一个数组{ index: i, value: arr[i] }，并按value字段进行排序：这个初始步骤使用**O（n）额外空间和O（n.log（n））**时间。
• 对于任何给定的端点对和目标总和：从排序数组的两端进行线性扫描，跳过索引在端点之外的元素，以线性时间找到对的计数。

下面是int数组的实现：

#include <stdlib.h>

struct array_values {
    size_t index;
    int value;
};

static int array_values_compare(const void *aa, const void *bb) {
    const struct array_values *a = aa;
    const struct array_values *b = bb;
    return (a->value > b->value) - (a->value < b->value);
}

struct array_values *sum_initialize(const int *arr, size_t n) {
    struct array_values *av = malloc(sizeof(*av) * n);
    for (size_t i = 0; i < n; i++) {
        av[i].index = i;
        av[i].value = arr[i];
    }
    qsort(av, n, sizeof(*av), array_values_compare);
    return av;
}

/* get the count of pairs whose sum is sum for subarray arr[start : end]
 * start index is included, end index is excluded.
 */
size_t sum_query(struct array_values *av, size_t n, size_t start, size_t end, int sum) {
    size_t i, j, count = 0;
    if (n > 0) {
        for (i = 0; j = n - 1; i < j; i++) {
            if (av[i].index >= start && av[i].index < end) {
                while (j > i && av[i].value + av[j].value > sum) {
                    j--;
                }
                while (j > i && av[i].value + av[j].value == sum) {
                    if (av[j].index >= start && av[j].index < end)
                        count++;
                    j--;
                }
            }
        }
    }
    return count;
}

一种算法，用于找出给定子阵列中和等于确定目标和的对的数量：
1.创建一个Map来存储数组中每个数字的频率。
1.对于每个元素，检查它是否可以与任何其他元素组合（除了它自己！）以给予所需的总和。相应地增加计数器。

1. 2.把计数除以2，然后返回（为什么？）因为每一对都被计算两次。）
   编辑1：这是我的python解决方案。它也可以使用集合来完成。

s=set()
result=set()
for item in a:
    target=original_target-i
    if target not in s:
       s.add(i)
    else:
        result.add((i,target))
print(len(result))

在Python中，注解集被实现为哈希表，所以除非加载因子太高，否则搜索将花费O（1）时间。所以总的复杂度是O（n）

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>>  pairSum(vector<int> &arr, int s){
    int n = arr.size();
    vector<vector<int>>pairs;
 for(int i=0; i<=n;i++)
 {
    for(int j=i+1;j<=n;j++)
    {
       if((arr[i]+arr[j]) == s)
       {
         vector<int> pair = {arr[i], arr[j]};
         pairs.push_back(pair);
       }
    }
 }
 return pairs;
}

一种内存消耗量很大的方法：
给定一个长度为n的数组values和一个目标和sum。
确定 * 小于 、 等于 * 和 * 大于 * sum/2的元素的计数-如果需要 * 有序 * 对的数量，则可能需要特殊处理 * 等于 * 的元素。
对于无序对 * 的索引 *：
假设 * 较小 * 不大于 * 较大 *。
对于values中不超过sum/2的每个值x，保持一个数据结构，允许确定x在values中出现的次数在给定范围内，例如，长度为n的数组，其计数在给定索引之前。
对于每一个查询，将子数组的值x重新排序。
累计起点和终点sum - x的计数;如果x等于sum/2，则减去1（这可以在预先计算中考虑）。