[BOJ] 3151. 합이 0 - c++

https://www.acmicpc.net/problem/3151

풀이 1 투포인터 => 시간초과

int main()
{
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N;
	cin>>N;
	long long answer=0;
	
	for (int i = 0; i < N; i++) {
		cin >> v[i];
	}
	sort(v,v+N);
    
    for(int i=0;i<N-2;i++){
        int lo=i+1;
        int hi=N-1;
        int tar = v[i]*(-1);
        while(lo<hi){
            int sum = v[lo]+v[hi];
            if(sum<tar) lo++;
            else if(sum==tar){//세 값의 합이 0인 경우
                if(v[lo]==v[hi]) answer+=hi-lo;//[-5 0 5(lo) 5 5(hi)]와 같은 경우
                else{//[-3 2 1 1 1]과 같은 경우 
                    int tmp = hi;
                    while(tmp>lo && v[tmp-1]==v[hi])tmp-=1;
                    answer+=(hi-tmp+1);
                }   
                lo++;
            }
            else hi--;
        }
    }
    cout<<answer;
    return 0;
}

풀이 2 upper_bound, lower_bound 사용 풀이

lower_bound = 목표값을 포함한 인덱스를 리턴
upper_bound = 목표보다 +1 값의 인덱스를 리턴

for(int i=0;i<n;++i)cin>>arr[i];
    sort(arr,arr+n);
 
    for(int i=0;i<n-2;++i){
        for(int j=i+1;j<n-1;++j){
            temp=(-1)*(arr[i]+arr[j]);
            first=lower_bound(arr+j+1,arr+n,temp)-arr;
            last=upper_bound(arr+j+1,arr+n,temp)-arr;
            answer+=last-first;
        }
    }