python - 减少数组上 python 问题的嵌套循环

Question

for _ in range(int(input())):
    num=int(input())
    a=list(map(int,input().split()))[:num]
    sum=0
    for i in range(len(a)):
        j=a[i]
        count=0
        key=0
        for k in range(len(a)):
            if j==a[k]:
                key=k
        sum+=abs(key-i)
    print(sum)

给定一个整数数组。任务是计算数组中存在的每个整数的第一次和最后一次出现的索引的绝对差之和。

需要计算数组中出现的每个此类问题的答案总和。

一个输入:

1 2 3 3 2

示例输出:

4

说明:数组中出现的元素是1,2,3。

1. 它只发生过一次，因此 1 的答案是 0。
2. 它在 2 和 5 处出现了两次，因此 |5-2|=3
3. 它在 3 和 4 处出现了两次，因此 |4-3|=1。

总共sum=0+3+1=4。 p.s:第一个循环用于测试用例。

请建议我降低时间复杂度。

Answer 1

最初，您可以创建一个唯一数字的字典并附加每个数字的所有索引，然后在第二个循环中您可以获得每个整数的差异。

for _ in range(int(input())):
    num=int(input())
    a=list(map(int,input().split()))[:num]
    sum=0
    nums = {}
    for i in range(len(a)):
        j=a[i]
        if j not in nums:
            nums[j] = []
        
        nums[j].append(i)
    
    for key in nums:
        sum += abs(nums[key][-1] - nums[key][0])
    print(sum)