Two sum

Two sum is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Task

Given a sorted array of single positive integers, is it possible to find a pair of integers from that array that sum up to a given sum? If so, return indices of the two integers or an empty array if not.

Example

Given numbers = [0, 2, 11, 19, 90], sum = 21,
Because numbers[1] + numbers[3] = 2 + 19 = 21,
return [1, 3].

Source

Stack Overflow: Find pair of numbers in array that add to given sum

C#

<lang csharp>public static int[] TwoSum(int[] numbers, int sum) {

   var map = new Dictionary<int, int>();
   for (var i = 0; i < numbers.Length; i++)
   {
      	var key = sum - numbers[i];
      	if (map.ContainsKey(key))
           return new[] { map[key], i };
       map.Add(numbers[i], i);
   }
   return Array.Empty<int>();

}</lang>

Output:

[0,3]

ooRexx

<lang oorexx>a=.array~of(0, 2, 11, 19, 90) x=21 do i=1 To a~items

 If a[i]>x Then Leave
 Do j=i+1 To a~items
   s=a[i]
   s+=a[j]
   Select
     When s=x Then Leave i
     When s>x Then Leave j
     Otherwise Nop
     End
   End
 End

If s=x Then Do

 i-=1            /* array a's index starts with 1, so adjust */
 j-=1
 Say '['i','j']'
 End

Else

 Say '[] - no items found'</lang>

Output:

[1,3]

REXX

<lang rexx>list=0 2 11 19 90 Do i=0 By 1 Until list=

 Parse Var list a.i list
 End

n=i-1 x=21 do i=1 To n

 If a.i>x Then Leave
 Do j=i+1 To n
   s=a.i
   s=s+a.j
   Select
     When s=x Then Leave i
     When s>x Then Leave j
     Otherwise Nop
     End
   End
 End

If s=x Then

 Say '['i','j']'

Else

 Say '[] - no items found'</lang>

Output:

[1,3]

zkl

I think this is O(n!), The double loop solution is O(n^2). <lang zkl>fcn twoSum(sum,ns){

  Utils.Helpers.combosKW(2,ns).filter('wrap([(a,b)]){ a+b==sum })  // lazy combos
  .apply('wrap([(a,b)]){ return(ns.index(a),ns.index(b)) })

}</lang> <lang zkl>fcn twoSum2(sum,ns){

  rs:=List();
  foreach i,j in (ns.len(),i){
     if(ns[i] + ns[j] == sum) rs.append(T(i,j));
  }
  rs

}</lang> <lang zkl>twoSum(21,T(0,2,11,19,90,21)).println(); twoSum(25,T(0,2,11,19,90,21)).println();</lang>

Output:

L(L(0,5),L(1,3))
L()