今天开始把算法学习时候的一些总结记录在博客,争取经过一段时间之后有一套系统化的学习总结。
今天学习枚举算法:
参考https://oi-wiki.org/basic/enumerate/
最后的优化:
// 要求 a 数组中的数的绝对值都小于 MAXN
bool met[MAXN * 2];
// 初始化 met 数组为 0;
memset(met, 0, sizeof(met));
for (int i = 0; i < n; ++i) {
if (met[MAXN - a[i]]) ++ans;
// 为了避免负数下标
met[a[i] + MAXN] = 1;
}
解读:
if (met[MAXN - a[i]])如果满足,说明a[i] + MAXN被记录过一次,也就是a[i]的相反数(-a[i])在前面出现过,所以能构成一对相反数。