use strict;
use warnings;

my @tests = (
    [[2,7,11,15], 9, 0, 1],
    [[2,7,11,15], 9, 1, 0],
    [[3,2,4], 6, 1, 2],
    [[3,2,4], 6, 2, 1],
    [[3,3], 6, 0, 1],
    [[3,3], 6, 1, 0],
    [[3,3,3,3,3,1,3,2,3,3,3,3], 3, 5, 7],
    [[3,3,3,3,3,1,3,2,3,3,3,3], 3, 7, 5],
    [[7,7,9,2,8,7,4,2], 13, 2, 6],
    [[7,7,9,2,8,7,4,2], 13, 6, 2],
);

my $count = 1;

for(@tests) {
 my $ret = two_sum($_->[0], $_->[1]);

 #check the result for correctness.
 if( ($$ret[0] == $_->[2] && $$ret[1] == $_->[3])
        ||
     ($$ret[1] == $_->[2] && $$ret[0] == $_->[3]) ){  print "ok $count\n" }
 else {
   print "@$ret\n";
   print "not ok $count\n";
 }

 $count++;
}

sub two_sum {

  my ($input, $target) = (shift, shift);

  # keep track of the original indices of the values,
  # prior to sorting the values.
  my %h;
  for(my $i = 0; $i < @$input; $i++) {
    # If the same value occurs twice, then 
    # either they both form the solution, or
    # neither is part of the solution.
    # Any value that occurs more than twice
    # cannot be part of the solution.
    if(exists $h{$$input[$i]} ) {
      return [$h{$$input[$i]}, $i]
       if $target == $$input[$i] * 2;

      next; # not part of the solution and therefore
            # no need to test that value any further.
    } 
    $h{$$input[$i]} = $i;
  }

  # Now let's sort the values.
  my @in = sort {$a <=> $b} keys(%h);

  my ($lo, $hi) = (0, @in - 1);

  for(;;) {
    # eliminate one value at each iteration
    my $cmp = ($in[$lo] + $in[$hi]) <=> $target;
    if   ($cmp < 0) { $lo++ }
    elsif($cmp > 0) { $hi-- }
    else {
      # return the indices of the given values.
      return [ $h{$in[$lo]}, $h{$in[$hi]} ];
    }
    # Safeguard against non-conforming inputs:
    die "Bad input array" if $lo >= $hi;
  }
}