在大小为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并计算它们之间的对数.