4个数和为0（二分）

ゞ浴缸里的玫瑰 2023-07-05 13:16 1阅读 0赞

给出N个整数，你来判断一下是否能够选出4个数，他们的和为0，可以则输出"Yes"，否则输出"No"。

Input

第1行，1个数N，N为数组的长度(4 <= N <= 1000) 第2 - N + 1行：Aii（-10^9 <= Aii <= 10^9)

Output

如果可以选出4个数，使得他们的和为0，则输出"Yes"，否则输出"No"。

Sample Input  
5  
\-1  
1  
\-5  
2  
4  
Sample Output  
Yes

暴力的话n^4 TLE  
我做的时候写的深搜+剪枝 也TLE 就是如果找的四个数都是负数或者都是正数跳过，如果正数负数各一半的话，超时了…  
TLE代码：

#include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const int maxn=1e3+10;
    ll a[maxn],n,sum,vis[maxn],flag=0;
    void dfs(ll step)
    { 
    	if(step==5)
    	{ 
    		if(sum==0)
    		{ 
    			flag=1;
    			return;
    		}
    		else	
    			return;
    	}
    	for(int i=1;i<=n;i++)
    	{ 
    		if(step==1&&a[i]>=0) break;
    		if(step==4&&a[i]<=0&&sum<=0) break; 
    		if(vis[i]==0)
    		{ 
    			sum+=a[i];
    			vis[i]=1;
    			dfs(step+1);
    			sum-=a[i];
    			vis[i]=0;
    		}
    	}
    }
    int main()
    { 
    	cin>>n;
    	ll num=0;
    	for(int i=1;i<=n;i++)
    	{ 
    		cin>>a[i];
    		if(a[i]<0) num++;
    	}
    	if(num==0||num==n)
    		cout<<"No"<<endl; 
    	sum=0;
    	sort(a+1,a+n+1);
    	dfs(1);
    	if(flag)
    		cout<<"Yes"<<endl;
    	else
    		cout<<"No"<<endl; 
    	return 0;
    }

正确解法：对整个数组排序，便于二分。枚举前两个数，二分查找后两个数的和，看四个数是否为0。n \* n \* log2(n)

#include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const int maxn=1e3+10;
    ll a[maxn];
    
    int main()
    { 
    	ios::sync_with_stdio(false);
    	ll n,flag=0;
    	cin>>n;
    	ll sum=0;
    	for(int i=1;i<=n;i++)
    	{ 
    		cin>>a[i];
    	}
    	sort(a+1,a+n+1);
    	for(int i=1;i<=n;i++)
    	{ 
    		for(int j=i+1;j<=n;j++)
    		{ 
    			sum=a[i]+a[j];
    			sum*=-1;
    			ll l=j+1,r=n;
    			while(l<r)
    			{ 
    				if(a[l]+a[r]==sum)
    				{ 
    					flag=1;
    					break;
    				}
    				else if(a[l]+a[r]<sum)
    					l++;
    				else
    					r--;
    				if(flag==1) break;
    			}
    			if(flag==1) break;
    		}
    		if(flag==1) break;
    	}
    	if(flag)
    		cout<<"Yes"<<endl;
    	else
    		cout<<"No"<<endl; 
    	return 0;
    }