c++ - 在大小为 n 的数组中查找索引 i<j ，以便这些索引处的值之和等于 i + j

Question

我的解决方案:

#include <bits/stdc++.h>

int main() {
    int n;//Size of array
    std::cin>>n;
    std::vector<long long>vec_int;
    int temp = n;
    while(n--){
        long long k ;
        std::cin>>k;
        vec_int.push_back(k);
    }
    n = temp;
    int num = 0;
    for(int  i = 0 ; i < n-1 ; i++){
        for(int j = i+1; j<n; j++){
            if(i<j && i+j == vec_int[i]+vec_int[j])
                num++;
        }
    }

    std::cout<<num;

    return 0;
}

我正在扫描大约需要 O(n^2) 时间的数组。在非常大的阵列上，问题的时间限制超过 2 秒的持续时间。我尝试对数组进行排序，但没有走得太远。我怎样才能加快速度？是否有可能在 O(n) 时间复杂度内做到这一点。

Answer 1

考虑重新定义您的问题。表达式:

i+j == vec_int[i]+vec_int[j]

在代数上等价于:

vec_int[i] - i == -(vec_int[j] - j)

所以定义:

a[i] = vec_int[i] - i

现在的问题是计算 a[i] == -a[j] 的次数。

这可以在 O(n) 中进行测试。使用 unordered_map m 计算每个负值在 a 中出现的次数。然后对于每个正值 a[i] 将与 m[-a[i]] 负值配对。还要计算 a 中零的数量并计算它们之间的对数。