New OJ 2008: 三数之和（左右指针）

题目链接：点击这里

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<unordered_map>

using namespace std;
typedef long long ll;

int a[5010];
 
int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	
	for(int i = 0; i < n; ++i)
		scanf("%d", &a[i]);
	
	sort(a, a+n);
	
	ll ans = 0;
	
	for(int i = 0; i < n; ++i)
	{
		int pivot = m - a[i];
		
		int L = i + 1, R = n - 1;
		
		while(L<R)
		{
			if(a[L] + a[R] == pivot)
			{
				if(a[L]==a[R])		//若相等，记录组合数
				{
					int len = R - L + 1;
					ans += (ll)len * (len-1) / 2;		 
					
					L += len;
					R -= len;
				}
				else				//若不相等，记录a[L]的个数乘a[R]的个数 
				{
					int cntL = 1, p = L + 1;
					while(a[p]==a[L])	cntL++, p++;
					
					int cntR = 1, q = R - 1;
					while(a[q]==a[R])	cntR++, q--;
					
					ans += cntL * cntR;
					
					L += cntL;
					R -= cntR;
				}
			}
			else if(a[L] + a[R] < pivot)
			{
				L++;
			}
			else
			{
				R--;
			}	
		}
	}
	
	printf("%lld\n", ans);
	return 0;
}