当前位置: 代码迷 >> 综合 >> 如何实现O(n)的2-sum
  详细解决方案

如何实现O(n)的2-sum

热度:67   发布时间:2024-01-18 23:48:51.0

2-sum问题 实现找数组中的二元数组(a,b)(a+b=0)

方法一:

循环 O(n2)

方法二:二分查找:

for(int i =0 ; i < n; i++){
Binary_Search(-a[i]);

}

结果 O(nlogn)

方法三:牺牲空间换取时间 基数排序算法

比如10^8内的整数

a[10^8]=0或者1

如果是1的话,代表在,如果是0,代表不存在

遇到一个数字的时候,在数组中比较是否存,就可以实现O(1)

for(int i =0 ; i<n ;i++){
if(a[i] == 1) 存在;

else 不存在;

}




  相关解决方案