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;
  }
}
[download]

Cheers,
Rob

Update:
When I first looked at this challenge, I noticed that the values in the first example were ordered from lowest to highest - which enables the opportunity to halve the maximum number of trial additions that will be needed. (This could be quite a saving on lengthy arrays of values.)
So I went ahead and coded up a procedure that worked quite nicely on sorted arrays.
Then I noticed that there was no guarantee that the input arrays would be pre-sorted.

Ok ... I'll just have to sort the input array first. (And don't worry that the cost of doing that probably outweighs the advantage of reduced additions.)
And then I woke up to the fact that I had to return the indices of the 2 values, not the 2 actual values.
Ok ... I can pre-process the original input array so that I keep track of the indices of the values, and then return the appropriate index values.
While doing this, I can remove duplicates from the input array - so it's not all additional cost.

By the time I finished, I felt like the only man to not Escape from Stalag Luft 112B.
But I posted anyway - as testament to the dangers of obstinacy and determination ;-)