不要相信“‘不同’的正整数”

这道题的内存实在小，小得只能开两个1e6数组

呜呜，我的map

方法1

思路：

1.i<j只是说明不能自己×自己（在sort排序之后该算还是得算）

2.假如有sa个a和sb个b（a≠b且a+b=x），根据乘法原理，就得到了sa×sb个数对

3.假如存在a=x/2，根据乘法原理，就得到了sa×(sa-1)/2个数对（比如{2,2,2,2}, x=4,每两个数都可以组成一个数对）

4.因为要维护和不变，可以用双指针把右端点和左端点同时向中间移动

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        b[a[i]]++;//b数组记录每一个数的出现次数
    }
    cin >> x;
    if (x % 2 == 0 && b[x / 2] > 0)
        ans += b[x / 2] * (b[x / 2] - 1) / 2;//见思路3
    sort(a+1, a+n+1);
    n = unique(a+1, a+n+1) - a - 1;//unique函数的作用是去重
    int i = 1, j = n;
    while (i < j)
    {
        if (a[i] + a[j] == x)
            ans+=b[a[i++]] * b[a[j--]];//如果刚好和等于x，就把ans+=a[i]的个数×a[j]的个数
        else if (a[i] + a[j] > x) 
            j--;//如果和大了，把右端点向左移
        else
            i++;//如果和小了，把左端点向右移
    }
    cout << ans;
}

这一段代码是用数组存的，其实也可以用set，可以省去排序和去重 也没省多少

方法2

短得离谱

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cin >> x;
    for (int i = 1; i <= n; i++)
    {
        ans += b[x - a[i]];//加上（x-a[i]）的个数
        b[a[i]]++;//这两行的顺序不能换，因为不能自己×自己
    }
    cout << ans;
}