顺带一提map的单次查询复杂度是O(logn)
所以你的AC代码的复杂度应该是O(nlogn)
unordered_map 的单次查询复杂度是O(1)
用unordered_map的话,复杂度就是O(n)
by Sicosuki @ 2023-11-07 10:14:12
你二分的边界不对,将二分过程修改如下
```
while(l<r){
略...
else r = mid
}
```
这样子可以得到84分,TLE两个点
原因是在有大量相同的数字的情况下(如 2 2 ...(很多个2) 2 4 6)
```
while(res+m==a[l++]) ans++;
```
这句话会严重拖慢速度,最差应该是O(n^2)的
有两种解决办法
1.再二分一次右边界
2.复制一份原数组,去重之后再二分
by Sicosuki @ 2023-11-07 10:15:49
@[Lazy_Durant](/user/1138579)
by Sicosuki @ 2023-11-07 10:16:32
@[Sicosuki](/user/914358) unordered_map 也不是单次 $O(1)$ 的好吧
by diqiuyi @ 2023-11-07 10:18:41
@[diqiuyi](/user/324666) 严格来说是**平均**单次$O(1)$
sorry,是我不够严谨
by Sicosuki @ 2023-11-07 10:26:20
@[Sicosuki](/user/914358)
谢谢大佬
by Lazy_Durant @ 2023-11-07 11:47:41