#!/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;
  }