3SUM

Problem Description
Given an array of positive and negative integers, find three that sum to zero.

Solution

import java.util.*;

public class Main {

	public static void main(String arg[]) {
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		long D[] = new long[N];
		Hashtable<Long, Integer> hash = new Hashtable<Long, Integer>();
		for(int i=0;i<N;i++) {
			D[i] = in.nextLong();
			if(hash.get(D[i])==null) {
				hash.put(D[i], 1);
			}
			else {
				hash.put(D[i], hash.get(D[i])+1);
			}
		}
		for(int i=0;i<N;i++) {
			for(int j=i+1;j<N;j++) {
				long D3 = -(D[i]+D[j]);
				if(hash.get(D3)!=null) {
					if(D[i]==D3 || D[j]==D3) {
						if(hash.get(D3)>1) {
							System.out.println(D[i]+" "+D[j]+" "+D3);
						}
					}
					else {
						System.out.println(D[i]+" "+D[j]+" "+D3);
					}
				}
			}
		}
	}
}
About these ads
Posted in Prog. Compettion

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 31 other followers