import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Map;
class start
{
private int desiredSum;
HashMap <Integer,Integer> subset;
HashMap <Integer,ArrayList<Integer>> valueIndices;
start()
{
super();
desiredSum = 9;
int integers[] = { -4, 8, 6, -4, 3, 6 };
System.out.println( "Looking for sums to " + desiredSum );
System.out.println( "Originally " + display( integers ));
mapValuesToIndexes( integers );
displayIndices( valueIndices );
for( int i=0; i<integers.length; i++ )
{
int searchTarget = desiredSum - integers[i];
if( valueIndices.containsKey( searchTarget ) )
{
ArrayList<Integer> indices = valueIndices.get( searchTarget );
System.out.println(
"[" + i + "]=" + integers[i] + " + "
+ searchTarget + "=" + indices.toString() );
}
}
}
public static void main( String args[])
{
start s = new start();
}
private static String display( int a[] )
{
StringBuilder strb = new StringBuilder();
String newline = System.getProperty( "line.separator" );
for( int i=0; i<a.length; i++ )
{
strb.append( a[i] + "," );
}
strb.append( newline );
return strb.toString();
}
private void mapValuesToIndexes( int a[] )
{
int index;
int value;
valueIndices = new HashMap <Integer,ArrayList<Integer>> ();
for( int i=0; i<a.length; i++ )
{
index = i;
value = a[i];
if( valueIndices.containsKey( value ) )
{
ArrayList<Integer> indices = valueIndices.get( value );
indices.add( index );
System.out.println( " duplicate value " + a[i] );
}else
{
ArrayList<Integer> indices = new ArrayList<Integer>();
indices.add( index );
valueIndices.put( value , indices );
}
}
}
private void displayIndices( HashMap <Integer,ArrayList<Integer>> valueIndices )
{
// for( ArrayList<Integer> alist : valueIndices.values() )
Set <Map.Entry <Integer, ArrayList<Integer>> > s = valueIndices.entrySet();
Iterator <Map.Entry <Integer, ArrayList<Integer>> > it = s.iterator();
while( it.hasNext() )
{
Map.Entry <Integer, ArrayList<Integer>> mapEntry = it.next();
int value = mapEntry.getKey();
ArrayList<Integer> indices = mapEntry.getValue();
System.out.println( " value " + value + " size " + indices.size() + "=" + indices.toString() );
}
}
} //end class