查找给定范围内的所有数字对

Question

我有N个数字，让我们说20301530401520。现在我想找出在给定范围内有多少对数字。（L和R给定）。数字对=两个数字相同。我的方法：

Answer 1

如果你追求的是速度，而不是记忆，也许有一个更好的方法。

您可以使用一个集合作为辅助数据结构来查看是否找到了一个数字，然后简单地遍历数组。伪代码：

int numPairs = 0;
set setVisited;
for (int i = L; i < R; i++) {
  if (setVisited.contains(a[i])) {
    // found the second of a pair. count it up and reset.
    numPairs++;
    setVisited.remove(a[i]);
  } else {
    // remember that we saw this number, so we can spot the next pair.
    setVisited.add(a[i]);
}