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 ;-)

In reply to Re: LeetCode Problem #1 - Two Sum - Improve and/or discuss. by syphilis
in thread LeetCode Problem #1 - Two Sum - Improve and/or discuss. by kcott

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.