一个区间内不同元素的和

Question

考虑一个数组（从0开始的索引），我需要找出所有可能范围[i，n]中不同元素的总和，其中0< i < n。

例子：

arr={1,2,1,3}

sum_range[0,3]={1,2,3}=6
sum_range[1,3]={1,2,3}=6
sum_range[2,3]={1,3}=4
sum_range[3,3]={3}=3  

O(n^2)的解法是一种可能的解法，我也读过持久化线段树可以做到这一点，但是我找不到好的教程。

是否可以在少于O(N^2)的时间内解决？

如果有人指出持久化线段树，请解释或提供一些好的链接？

- nil96

---

dasblinkenlight的算法更好，但另一种策略是对范围内的数组部分进行排序（O(n log n)），然后遍历排序后的数组，同时对与前一个元素不同的元素求和（O(n)），从而得到总时间复杂度为O(n log n)。 - Jeff Irwin

Answer 1

使用简单的动态规划算法可以在O(n)时间内完成。

从数组末尾开始，使用基于哈希的容器存储已遇到的数字。最后一个元素的值，即sum_range[n-1]被设置为arr[n-1]。之后，sum_range[i]的值应按以下方式计算：

• 如果arr[i]不在已经出现的数字集合中，则sum_range[i] = sum_range[i+1]+arr[i]
• 否则， sum_range[i] = sum_range[i+1]

由于检查哈希容器是否存在某个值的成本为O(1)，添加一个项目到哈希容器的成本对于n个项目来说是摊销O(1)，因此这个算法的总成本是O(n)。

与使用O(1)空间的O(n²)算法相比，该算法使用额外的O(n)空间用于哈希容器。

- Sergey Kalinichenko

---

你有哈希表插入和查找复杂度的来源吗？我一直听说这最多是O(log(n))，因为会出现冲突。我找不到任何支持或反对这个观点的来源。 - Diane M

@ArthurHavlicek 哈希表：性能分析 - Sergey Kalinichenko

Answer 2

对数组进行切片（O(n)），然后使用集合并将值添加到集合中。

在Python3.x代码中，根据评论进行了编辑：

array = [1, 2, 1, 3, 5]
range_sum = 0
total_sum = 0
valueset = set ()
for val in reversed(array):
    if val not in valueset :
        valueset.add (val)
        range_sum += val
    total_sum += range_sum

print (total_sum)

- Diane M

---

你在哪里使用集合得到log n？ - Untitled123

OP要求“所有可能的区间[i，n]中不同元素的总和”。这并没有回答这个问题。 - Juan Lopes

Answer 3

有多种方法可以解决这个问题。

1. 使用 Arrays.sort(); 对数组进行排序。

2. 使用 set

   long sumOfDistinct(long arr[], int N)
   {
        int size = arr.length;
        HashSet<Long> unique = new HashSet<Long>(); 
        long sum = 0;
        for(int i=0;i<size;i++){
                if(!unique.contains(arr[i])){
                    sum = sum + arr[i];
                    unique.add(arr[i]);
                }
        }
   
        return sum;
    }
   

- Pradeep Mishra