sub twosum_NetWallah{
  my ($inp, $target)=@_;
  my %targ_idx = map { $inp->[$_] => $_ } 0..$#$inp;

  for (0..$#$inp){
     next unless defined ( my $other=$targ_idx{ $target - $inp->[$_] }
+ );
     next if $other == $_;
     return [ $other > $_ ? ($_, $other) : ($other, $_) ];
  }
  return undef;
}    

# Test NetWallah..
for my $test (@tests) {
    is_deeply
        sort_arrayref(twosum_NetWallah ($test->[INPUT], $test->[TARGET
+])),
        sort_arrayref($test->[EXPECTED]);
}
[download]

UPDATE 2: I did try to benchmark the code - kcott's runs ~ 40% faster, so I was surprised!
However- After adding this test case:

    [[-5,-3,1,4,7], 1, [1,3]],
[download]

BTW - thanks for setting up this challenge!

G'day NetWallah,

"After adding this test case: [[-5,-3,1,4,7], 1, [1,3]], kcott's code fails that test case, but mine passes."

Well spotted and thanks for reporting the bug.

I had added

next INNER if $input->[$j] > $target;
[download]

on the basis that a single comparison was less processing than the addition plus comparison in

if ($input->[$i] + $input->[$j] == $target) {
[download]

I thought that was a handy logic short-circuit; however, I hadn't taken into account negative numbers. I've removed that line and the INNER label: all tests now pass.

"Also - kcott's code assumes and takes advantage of the input being sorted - input order is NOT specified in the problem definition."

I don't know where you got that idea from. I neither made that assumption nor wrote any code taking advantage of such sorting. Note [[3,2,4], 6, [1,2]] which has unsorted input.

— Ken

This is O(N) instead of O(N^2), so it will scale better.

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]

O(N log N), O(N) if already sorted.

Rather than sorting the inputs, I would sort the indexes. That way, you wouldn't need an extra hash an array, just an array.

G'day Rob,

++ Perhaps consider it in the positive light of professionalism and perseverance.

I loved those Ripping Yarns shows when they came out in the mid to late '70s. From your link, I found others; further searching located the remainder. It looks like I've lined up several hours of Australia Day entertainment. :-)

— Ken

It looks like I've lined up several hours of Australia Day entertainment. :-)

That sure is a lot more appealing than waving flags ;-)

Cheers,
Rob

sub two_sum_choroba {
    my ($input, $target) = @_;
    my %seen;
    for my $i (0 .. $#$input) {
        my $x = $input->[$i];

        return [$i, $seen{ $target - $x }]
            if exists $seen{ $target - $x };

        $seen{$x} = $i;
    }
}
[download]

It passes all the tests presented in the thread so far and benchmarks show it's also the fastest.

Translated to Python 3 (Dona eis requiem, smack), it was accepted by LeetCode as

Runtime: 48 ms, faster than 99.40% of Python3 online submissions for T
+wo Sum.
Memory Usage: 15.4 MB, less than 42.44% of Python3 online submissions 
+for Two Sum.
[download]

#!/usr/bin/perl

use strict; # https://perlmonks.org/?node_id=11140759
use warnings;

use constant {
    INPUT => 0,
    TARGET => 1,
    EXPECTED => 2,
};

use Test::More;

my @tests = (
    [[2,7,11,15], 9, [0, 1]],
    [[15,11,7,2], 9, [2, 3]],
    [[-15,-11,-7,-2], -9, [2, 3]],
    [[3,2,4], 6, [1,2]],
    [[3,3], 6, [0,1]],
    [[-3,-3], -6, [0,1]],
    [[(1,6)x1995,3,5], 8, [3990,3991]], # for O(n**2) solutions
    [[-1,4, -4], 0, [1,2]],
);

plan tests => 0+@tests;

for my $test (@tests) {
    is_deeply
        two_sum($test->[INPUT], $test->[TARGET]),
        $test->[EXPECTED];
}

sub two_sum # O(n)
  {
  my ($input, $target) = @_;
  my (%h, $second);
  push @{ $h{$input->[$_]} }, $_ for 0 .. $#$input;
  $second = $h{$target - $_} and ($_ != $target - $_ or @$second > 1)
    and return [ $h{$_}[0], $second->[-1] ] for @$input;
  }
[download]

I believe this runs in O(n) time. But that's on the presumption that the input list of numbers is already sorted. If it's not, then this solution would have to add a sorting step, which will make it O(n log n).

sub TwoSum
{
    my( $target, @nums ) = @_;
    # assumption: @nums are already sorted.
    # caveat: the nums in the list might not be uniq!!!
    
    my %num; @num{@nums} = (); # for existence tests.

    for my $i2 ( reverse( 1 .. $#nums ) )
    {
        my $d = $target - $nums[$i2];
        if ( exists $num{$d} )
        { # gotta find the _first_ occurrence of this number in the li
+st:
            my($i1) = grep { $nums[$_] == $d } 0 .. $i2-1;
            return( $i1, $i2 );
        }
    }

    die
}
[download]

G'day jdporter,

I liked the general thinking behind this; however, I see two issues.

"# assumption: @nums are already sorted."

There is no requirement for the input list to be sorted. As an example, see "1. Two Sum" Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]
[download]

If you did "add a sorting step", you could potentially change the result:

Input: nums = [2,3,4], target = 6
Output: [0,2]
[download]

"# caveat: the nums in the list might not be uniq!!!"

Again, there's no requirement for this uniqueness. See Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]
[download]

As far as I can tell (by inspection) your code produces a correct result with this input. An input of [3,1,1,1,3] would produce a correct result: [0,4]. An input of [3,3,3] would be invalid from the outset, because there's more than one possible solution: [0,1], [0,2] and [1,2] — whatever code you (or anyone) wrote would be immaterial for this input.

— Ken

As already pointed out by kcott is the uniqueness of the solution guarantied. --> Re^8: LeetCode Problem #1 - Two Sum - Improve and/or discuss.

Hence no need for greping.

If the first occurrence was really required, I'd rather store it in the hash.

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}

The test is more complex than the code if you want to accept both [0,1] and [1,0] better and easier just rely on the expected sum. Anyway..

sub two_sum_Discipulus {
    my ($input, $target) = @_;
    foreach my $index ( 0 .. $#$input ){
        ( $_ != $index and $input->[$_] + $input->[$index] == $target 
+) ? 
                return [$index, $_]                                   
+  :   0 
                for 0 .. $#$input;
    }
}
[download]

PS added newlines for a minimal readability enhancement

L*

Both concise and weird. And no, it's not really golfed. I just wanted to see if this would work.

sub two_sum # O(n)
  {
  my ($i, $input, $target, %h) = (0, @_);
  return [ $h{$_} // ($h{$target - $_} = $i++, next), $i ] for @$input
+;
  }
[download]

nitpick:

I think

• You can return the answer in any order.

means you have to also allow the reverse order in your tests.

edit

this can be fixed by sorting the result first.

That's a fair enough comment: any order was specified in the problem spec. I added to @tests:

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

Modified is_deeply:

for my $test (@tests) {
    is_deeply
        sort_arrayref(two_sum($test->[INPUT], $test->[TARGET])),
        sort_arrayref($test->[EXPECTED]);
}
[download]

Appended a new subroutine:

sub sort_arrayref {
    my ($aref) = @_;

    return [ sort { $a <=> $b } @$aref ];
}
[download]

Output now:

1..6
ok 1
ok 2
ok 3
ok 4
ok 5
ok 6
[download]

— Ken

not sure why you are duplicating the tests ... (?)

one sort_arrayref(two_sum(...)) is enough if you only keep tests with already sorted expectations.

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}