c++ - 子数组中两个数字的相同出现(连续)

Question

给定一个整数数组，找到具有相同数量的 x 和 y 的连续子序列的总数。例如 x=1 和 y=2 的数组 [1,2,1] ans = 2 表示它的两个子数组 [1,2] 和 [2,1]。检查每个连续的子序列是 O(n^2)，效率太低。有什么改进的想法吗？

这是我写的代码

int get_total(int* a,int x,int y,int n){
    int result=0;
    for(int i=0;i<n;i++){
        int x_c=0,y_c=0;
        for(int j=i;j<n;j++){
            if(a[j]==x){
                x_c++;
            }
            if(a[j]==y){
                y_c++;
            }
            if(x_c==y_c){
                result++;
            }
        }
    }
    return result;
}

int main(){
    int n,q;
    cin >>n >>q;
    int a[n];
    for(int i=0;i<n;i++){
        cin >>a[i];
    }
    while(q--){
        int x,y;
        cin >>x >>y;
        cout <<get_total(a,x,y,n)<<"\n";
    }
}

它针对每个查询在 n^2 中运行。最大数组大小为 8*10^3，最大查询数为 10^5

Answer 1

创建一个辅助数组x_y_diffs，本质上是:

#(times_x_appeared_thus_far) - #(times_y_appeared_thus_far)

可以计算为:

x_y_diffs[0] = 0
x_y_diffs[i] = x_y_diffs[i-1] + 1         if array[i-1] == x
               x_y_diffs[i-1] - 1         if array[i-1] == y
               x_y_diffs[i-1]             otherwise

很容易看出它可以用线性时间计算。

现在，观察“好的”子序列 (i,j) 在 x_y_diffs[i+1] == x_y_diffs[j+1] 处开始和结束。

因此，您可以简单地迭代数组并维护一个直方图，计算每个值出现的次数。

std::map<int, int> histogram;
int count = 0;
for (int x : x_y_diffs) {
  count += histogram[x];
  histogram[x] = histogram[x] + 1;
}

这需要 O(nlogn) 时间来计算(每个映射插入/查找是 O(logn))，并且可以改进为 O(n ) 平均情况 从 std::map 切换到 std::unordred_map。

因此，该算法总共是 O(n) 或 O(nlogn) 时间(基于 map 选择)- 和 O(n) 额外的空间。

Demo on ideone