Two Sum

From Rosetta Code
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

Aime[edit]

integer i, u, v;
index x;
list l;
 
l_bill(l, 0, 0, 2, 11, 19, 90);
 
for (i, u in l) {
x[u] = i;
if (i_jack(v, x, 21 - u)) {
o_(v, " ", i, "\n");
break;
}
}
Output:
1 3

ALGOL 68[edit]

Translation of: Lua
# returns the subscripts of a pair of numbers in a that sum to sum, a is assumed to be sorted #
# if there isn't a pair of numbers that summs to sum, an empty array is returned #
PRIO TWOSUM = 9;
OP TWOSUM = ( []INT a, INT sum )[]INT:
BEGIN
BOOL found := FALSE;
INT i := LWB a;
INT j := UPB a;
WHILE i < j AND NOT found DO
INT s = a[ i ] + a[ j ];
IF s = sum THEN
found := TRUE
ELIF s < sum THEN
i +:= 1
ELSE
j -:= 1
FI
OD;
IF found THEN ( i, j ) ELSE () FI
END # TWOSUM # ;
 
# test the TWOSUM operator #
PROC print twosum = ( []INT a, INT sum )VOID:
BEGIN
[]INT pair = a[ AT 0 ] TWOSUM sum;
IF LWB pair > UPB pair THEN
# no pair with the required sum #
print( ( "[]", newline ) )
ELSE
# have a pair #
print( ( "[", whole( pair[ LWB pair ], 0 ), ", ", whole( pair[ UPB pair ], 0 ), "]", newline ) )
FI
END # print twosum # ;
print twosum( ( 0, 2, 11, 19, 90 ), 21 ); # should be [1, 3] #
print twosum( ( -8, -2, 0, 1, 5, 8, 11 ), 3 ); # should be [0, 6] (or [1, 4]) #
print twosum( ( -3, -2, 0, 1, 5, 8, 11 ), 17 ); # should be [] #
print twosum( ( -8, -2, -1, 1, 5, 9, 11 ), 0 ) # should be [2, 3] #
Output:
[1, 3]
[0, 6]
[]
[2, 3]

AppleScript[edit]

Translation of: JavaScript
Translation of: Haskell


Nesting concatMap or (>>=) (flip concatMap) yields the cartesian product of the list with itself. Skipping products where the y index is lower than the x index (see the use of 'drop' below) ignores the 'lower triangle' of the cartesian grid, excluding mirror-image and duplicate number pairs.

-- sumTo :: Int -> [Int] -> [(Int, Int)]
on sumTwo(n, xs)
set ixs to zip(enumFromTo(0, |length|(xs) - 1), xs)
 
script ijIndices
on |λ|(ix)
set {i, x} to ix
 
script jIndices
on |λ|(jy)
set {j, y} to jy
 
if (x + y) = n then
{{i, j}}
else
{}
end if
end |λ|
end script
 
|>>=|(drop(i + 1, ixs), jIndices)
end |λ|
end script
 
|>>=|(ixs, ijIndices)
end sumTwo
 
-- TEST ----------------------------------------------------------------------
on run
sumTwo(21, [0, 2, 11, 19, 90, 10])
 
--> {{1, 3}, {2, 5}}
end run
 
 
-- GENERIC FUNCTIONS ---------------------------------------------------------
 
-- (>>=) :: Monad m => m a -> (a -> m b) -> m b
on |>>=|(xs, f)
concat(map(f, xs))
end |>>=|
 
-- concat :: [[a]] -> [a] | [String] -> String
on concat(xs)
script append
on |λ|(a, b)
a & b
end |λ|
end script
 
if length of xs > 0 and class of (item 1 of xs) is string then
set empty to ""
else
set empty to {}
end if
foldl(append, empty, xs)
end concat
 
-- drop :: Int -> a -> a
on drop(n, a)
if n < length of a then
if class of a is text then
text (n + 1) thru -1 of a
else
items (n + 1) thru -1 of a
end if
else
{}
end if
end drop
 
-- enumFromTo :: Int -> Int -> [Int]
on enumFromTo(m, n)
if m > n then
set d to -1
else
set d to 1
end if
set lst to {}
repeat with i from m to n by d
set end of lst to i
end repeat
return lst
end enumFromTo
 
-- foldl :: (a -> b -> a) -> a -> [b] -> a
on foldl(f, startValue, xs)
tell mReturn(f)
set v to startValue
set lng to length of xs
repeat with i from 1 to lng
set v to |λ|(v, item i of xs, i, xs)
end repeat
return v
end tell
end foldl
 
-- length :: [a] -> Int
on |length|(xs)
length of xs
end |length|
 
-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
tell mReturn(f)
set lng to length of xs
set lst to {}
repeat with i from 1 to lng
set end of lst to |λ|(item i of xs, i, xs)
end repeat
return lst
end tell
end map
 
-- min :: Ord a => a -> a -> a
on min(x, y)
if y < x then
y
else
x
end if
end min
 
-- Lift 2nd class handler function into 1st class script wrapper
-- mReturn :: Handler -> Script
on mReturn(f)
if class of f is script then
f
else
script
property |λ| : f
end script
end if
end mReturn
 
-- zip :: [a] -> [b] -> [(a, b)]
on zip(xs, ys)
set lng to min(length of xs, length of ys)
set lst to {}
repeat with i from 1 to lng
set end of lst to {item i of xs, item i of ys}
end repeat
return lst
end zip
Output:
{{1, 3}, {2, 5}}

AutoHotkey[edit]

TwoSum(a, target){
i := 1, j := a.MaxIndex()
while(i < j){
if (a[i] + a[j] = target)
return i ", " j
else if (a[i] + a[j] < target)
i++
else if (a[i] + a[j] > target)
j--
}
return "not found"
}
Examples:
MsgBox % TwoSum([0, 2, 11, 19, 90], 21) ; returns 2, 4 (first index is 1 not 0)
Outputs:
2,4

AWK[edit]

 
# syntax: GAWK -f TWO_SUM.AWK
BEGIN {
numbers = "0,2,11,19,90"
print(two_sum(numbers,21))
print(two_sum(numbers,25))
exit(0)
}
function two_sum(numbers,sum, arr,i,j,s) {
i = 1
j = split(numbers,arr,",")
while (i < j) {
s = arr[i] + arr[j]
if (s == sum) {
return(sprintf("[%d,%d]",i,j))
}
else if (s < sum) {
i++
}
else {
j--
}
}
return("[]")
}
 
Output:
[2,4]
[]

C[edit]

 
/*Abhishek Ghosh, 23rd September 2017*/
 
#include<stdio.h>
 
int main()
{
int arr[5] = {0, 2, 11, 19, 90},sum = 21,i,j,check = 0;
 
for(i=0;i<4;i++){
for(j=i+1;j<5;j++){
if(arr[i]+arr[j]==sum){
printf("[%d,%d]",i,j);
check = 1;
break;
}
}
}
 
if(check==0)
printf("[]");
 
return 0;
}
 

Output :

[1,3]

C#[edit]

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>();
}
Output:
[1,3]

Dart[edit]

 
main() {
var a = [1,2,3,4,5];
var s=25,c=0;
var z=(a.length*(a.length-1))/2;
for (var x = 0; x < a.length; x++) {
print(a[x]);
}
for (var x = 0; x < a.length; x++) {
for(var y=x+1;y< a.length; y++)
{
if(a[x]+a[y]==s)
{
print([a[x],a[y]]);
break;
}
else
{
c++;
}
}
}
if(c==z)
{
print("such pair doesn't exist");
}
}
 
 
 

Elixir[edit]

defmodule RC do
def two_sum(numbers, sum) do
Enum.with_index(numbers) |>
Enum.reduce_while([], fn {x,i},acc ->
y = sum - x
case Enum.find_index(numbers, &(&1 == y)) do
nil -> {:cont, acc}
j -> {:halt, [i,j]}
end
end)
end
end
 
numbers = [0, 2, 11, 19, 90]
IO.inspect RC.two_sum(numbers, 21)
IO.inspect RC.two_sum(numbers, 25)
Output:
[1, 3]
[]

Forth[edit]

Works with: Gforth version 0.7.3
CREATE A CELL ALLOT
: A[] ( n -- A[n]) CELLS A @ + @ ;
:NONAME 1- ;
:NONAME R> DROP R> DROP TRUE ;
:NONAME SWAP 1+ SWAP ;
CREATE VTABLE , , ,
: CMP ( n n' -- -1|0|1) - DUP IF DUP ABS / THEN ;
: (TWOSUM) ( addr n n' -- u1 u2 t | f)
>R SWAP A ! 0 SWAP 1- ( lo hi) ( R: n')
BEGIN OVER OVER < WHILE
OVER A[] OVER A[] + [email protected]
CMP 1+ CELLS VTABLE + @ EXECUTE
REPEAT
DROP DROP R> DROP FALSE ;
: TWOSUM ( addr n n' --) [CHAR] [ EMIT
(TWOSUM) IF SWAP 0 .R [CHAR] , EMIT SPACE 0 .R THEN
[CHAR] ] EMIT ;
CREATE TEST0 0 , 2 , 11 , 19 , 90 , DOES> 5 ;
CREATE TEST1 -8 , -2 , 0 , 1 , 5 , 8 , 11 , DOES> 7 ;
TEST0 21 TWOSUM CR
TEST0 25 TWOSUM CR
TEST1 3 TWOSUM CR
TEST1 8 TWOSUM CR
BYE
Output:
[1, 3]
[]
[0, 6]
[2, 5]

FreeBASIC[edit]

' FB 1.05.0 Win64
 
' "a" is the array of sorted non-negative integers
' "b" is the array to contain the result and is assumed to be empty initially
 
Sub twoSum (a() As UInteger, b() As Integer, targetSum As UInteger)
Dim lb As Integer = LBound(a)
Dim ub As Integer = UBound(a)
If ub = -1 Then Return '' empty array
Dim sum As UInteger
 
For i As Integer = lb To ub - 1
If a(i) <= targetSum Then
For j As Integer = i + 1 To ub
sum = a(i) + a(j)
If sum = targetSum Then
Redim b(0 To 1)
b(0) = i : b(1) = j
Return
ElseIf sum > targetSum Then
Exit For
End If
Next j
Else
Exit For
End If
Next i
End Sub
 
Dim a(0 To 4) As UInteger = {0, 2, 11, 19, 90}
Dim b() As Integer
Dim targetSum As UInteger = 21
twoSum a(), b(), targetSum
If UBound(b) = -1 Then
Print "No two numbers were found whose sum is "; targetSum
Else
Print "The numbers with indices"; b(LBound(b)); " and"; b(UBound(b)); " sum to "; targetSum
End If
Print
Print "Press any number to quit"
Sleep
Output:
The numbers with indices 1 and 3 sum to 21

Haskell[edit]

Returning first match[edit]

twoSum::(Num a,Ord a) => a -> [a] -> [Int]
twoSum num list = sol ls (reverse ls)
where
ls = zip list [0..]
sol [] _ = []
sol _ [] = []
sol xs@((x,i):us) ys@((y,j):vs) = ans
where
s = x + y
ans | s == num = [i,j]
| j <= i = []
| s < num = sol (dropWhile ((<num).(+y).fst) us) ys
| otherwise = sol xs $ dropWhile ((num <).(+x).fst) vs
 
main = print $ twoSum 21 [0, 2, 11, 19, 90]
Output:
[1,3]

Returning all matches[edit]

Listing multiple solutions (as zero-based indices) where they exist:

sumTo :: Int -> [Int] -> [(Int, Int)]
sumTo n ns =
let ixs = zip [0 ..] ns
in ixs >>=
(\(i, x) ->
drop (i + 1) ixs >>=
\(j, y) ->
[ (i, j)
| (x + y) == n ])
 
main :: IO ()
main = mapM_ print $ sumTo 21 [0, 2, 11, 19, 90, 10]

Or, resugaring a little – pulling more into the scope of the list comprehension:

sumTo :: Int -> [Int] -> [(Int, Int)]
sumTo n ns =
let ixs = zip [0 ..] ns
in [ (i, j)
| (i, x) <- ixs
, (j, y) <- drop (i + 1) ixs
, (x + y) == n ]
 
main :: IO ()
main = mapM_ print $ sumTo 21 [0, 2, 11, 19, 90, 10]
Output:
(1,3)
(2,5)

Icon and Unicon[edit]

Translation of: Lua

Icon and Unicon are ordinal languages, first index is one.

fullimag library used to pretty print lists.

#
# twosum.icn, find two array elements that add up to a given sum
# Dedicated to the public domain
#
link fullimag
procedure main(arglist)
sum := pop(arglist) | 21
L := []
if *arglist > 0 then every put(L, integer(!arglist)) & L := sort(L)
else L := [0, 2, 11, 19, 90]
 
write(sum)
write(fullimage(L))
write(fullimage(twosum(sum, L)))
end
 
# assume sorted list, only interested in zero or one solution
procedure twosum(sum, L)
i := 1
j := *L
while i < j do {
try := L[i] + L[j]
if try = sum then return [i,j]
else
if try < sum then
i +:= 1
else
j -:= 1
}
return []
end
Output:
$ unicon -s twosum.icn -x
21
[0,2,11,19,90]
[2,4]

J[edit]

So, first off, our basic approach will be to find the sums:

   =+/~0 2 11 19 90
0 2 11 19 90
2 4 13 21 92
11 13 22 30 101
19 21 30 38 109
90 92 101 109 180

And, check if any of them are our desired value:

   21=+/~0 2 11 19 90
0 0 0 0 0
0 0 0 1 0
0 0 0 0 0
0 1 0 0 0
0 0 0 0 0

Except, we want indices here, so let's toss the structure so we can get those:

   ,21=+/~0 2 11 19 90
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
I.,21=+/~0 2 11 19 90
8 16

Except, we really needed that structure - in this case, since we had a five by five table, we want to interpret this result as a base five pair of numbers:

   $21=+/~0 2 11 19 90
5 5
5 5#:I.,21=+/~0 2 11 19 90
1 3
3 1

Or, taking advantage of being able to use verbs to represent combining their results, when we use three of them:

   ($ #: [email protected],)21=+/~0 2 11 19 90
1 3
3 1

But to be more like the other task implementations here, we don't want all the results, we just want zero or one result. We can't just take the first result, though, because that would fill in a 0 0 result if there were none, and 0 0 could have been a valid result which does not make sense for the failure case. So, instead, let's package things up so we can add an empty to the end and take the first of those:

   ($ <@#: [email protected],)21=+/~0 2 11 19 90
┌───┬───┐
1 33 1
└───┴───┘
a:,~($ <@#: [email protected],)21=+/~0 2 11 19 90
┌───┬───┬┐
1 33 1││
└───┴───┴┘
{.a:,~($ <@#: [email protected],)21=+/~0 2 11 19 90
┌───┐
1 3
└───┘
 ;{.a:,~($ <@#: [email protected],)21=+/~0 2 11 19 90
1 3

Finally, let's start pulling our arguments out using that three verbs combining form:

   ;{.a:,~($ <@#: [email protected],) 21([ = +/[email protected]])0 2 11 19 90
1 3
 ;{.a:,~21 ($ <@#: [email protected],)@([ = +/[email protected]])0 2 11 19 90
1 3

a: is not a verb, but we can use a noun as the left verb of three as an implied constant verb whose result is itself:

   ;{. 21 (a:,~ ($ <@#: [email protected],)@([ = +/[email protected]]))0 2 11 19 90
1 3

And, let's finish the job, give this a name, and test it out:

   twosum=: ;@{[email protected](a:,~ ($ <@#: [email protected],)@([ = +/[email protected]]))
21 twosum 0 2 11 19 90
1 3

Except that looks like a bit of a mess. A lot of the reason for this is that ascii is ugly to look at. (Another issue, though, is that a lot of people are not used to architecting control flow as expressions.)

So... let's do this over again, using a more traditional implementation where we name intermediate results. (We're going to stick with our architecture, though, because changing the architecture to the more traditional approach would change the space/time tradeoff to require more time.)

two_sum=:dyad define
sums=. +/~ y
matches=. x = sums
sum_inds=. I. , matches
pair_inds=. ($matches) #: sum_inds
 ; {. a: ,~ <"1 pair_inds
)

And, testing:

   21 two_sum 0 2 11 19 90
1 3

Or, we could go slightly more traditional and instead of doing that boxing at the end, use an if/else statement:

two_sum=:dyad define
sums=. +/~ y
matches=. x = sums
sum_inds=. I. , matches
pair_inds=. ($matches) #: sum_inds
if. #pair_inds do.
{.pair_inds
else.
i.0
end.
)

Then again, most people don't read J anyways, so maybe just stick with the earlier implementation:

twosum=: ;@{[email protected](a:,~ ($ <@#: [email protected],)@([ = +/[email protected]]))

Alternative approach

An alternative method for identifying and returning non-duplicate indicies of the pairs follows.

   21 (= +/~) 0 2 11 19 90
0 0 0 0 0
0 0 0 1 0
0 0 0 0 0
0 1 0 0 0
0 0 0 0 0

The array is symmetrical so we can zero one half to remove duplicate pairs and then retrieve the remaining indicies using sparse array functionality.

zeroLowerTri=: * [: </~ [email protected]#
getIdx=: 4 $. $.
twosum_alt=: [email protected]@(= +/~)

Testing ...

   21 twosum_alt 0 2 11 19 90
1 3

Java[edit]

Translation of: Lua
import java.util.Arrays;
 
public class TwoSum {
 
public static void main(String[] args) {
long sum = 21;
int[] arr = {0, 2, 11, 19, 90};
 
System.out.println(Arrays.toString(twoSum(arr, sum)));
}
 
public static int[] twoSum(int[] a, long target) {
int i = 0, j = a.length - 1;
while (i < j) {
long sum = a[i] + a[j];
if (sum == target)
return new int[]{i, j};
if (sum < target) i++;
else j--;
}
return null;
}
}
[1, 3]


JavaScript[edit]

ES5[edit]

Nesting concatMap yields the cartesian product of the list with itself, and functions passed to Array.map() have access to the array index in their second argument. Returning [] where the y index is lower than or equal to the x index ignores the 'lower triangle' of the cartesian grid, skipping mirror-image and duplicate number pairs. Returning [] where a sum condition is not met similarly acts as a filter – all of the empty lists in the map result are eliminated by the concat.

(function () {
var concatMap = function (f, xs) {
return [].concat.apply([], xs.map(f))
};
 
return function (n, xs) {
return concatMap(function (x, ix) {
return concatMap(function (y, iy) {
return iy <= ix ? [] : x + y === n ? [
[ix, iy]
] : []
}, xs)
}, xs)
}(21, [0, 2, 11, 19, 90]);
})();
 
Output:
[[1,3]]

ES6[edit]

Composing a solution from generic functions like zip, bind (>>=, or flip concatMap) etc.

Translation of: Haskell
(() => {
'use strict';
 
// SUMTWO ----------------------------------------------------------------
 
// sumTwo :: Int -> [Int] -> [(Int, Int)]
function sumTwo(n, xs) {
const ixs = zip(enumFromTo(0, length(xs) - 1), xs);
return bind(ixs,
([i, x]) => bind(drop(i + 1, ixs),
([j, y]) => (x + y === n) ? [
[i, j]
] : []
)
);
};
 
// GENERIC FUNCTIONS -----------------------------------------------------
 
// bind (>>=) :: [a] -> (a -> [b]) -> [b]
const bind = (xs, f) => [].concat.apply([], xs.map(f));
 
// drop :: Int -> [a] -> [a]
const drop = (n, xs) => xs.slice(n);
 
// enumFromTo :: Int -> Int -> [Int]
const enumFromTo = (m, n) =>
Array.from({
length: Math.floor(n - m) + 1
}, (_, i) => m + i);
 
// length :: [a] -> Int
const length = xs => xs.length;
 
// show :: a -> String
const show = (...x) =>
JSON.stringify.apply(
null, x.length > 1 ? [x[0], null, x[1]] : x
);
 
// zip :: [a] -> [b] -> [(a,b)]
const zip = (xs, ys) =>
xs.slice(0, Math.min(xs.length, ys.length))
.map((x, i) => [x, ys[i]]);
 
 
// TEST ------------------------------------------------------------------
return show(
sumTwo(21, [0, 2, 11, 19, 90, 10])
);
})();
Output:
[[1,3],[2,5]]

Julia[edit]

Works with: Julia version 0.6
Translation of: Python
function twosum(v::Vector, s)
i = 1
j = length(v)
while i < j
if v[i] + v[j] == s
return [i, j]
elseif v[i] + v[j] < s
i += 1
else
j -= 1
end
end
return similar(v, 0)
end
 
@show twosum([0, 2, 11, 19, 90], 21)
Output:
twosum([0, 2, 11, 19, 90], 21) = [2, 4]

Kotlin[edit]

// version 1.1
 
fun twoSum(a: IntArray, targetSum: Int): Pair<Int, Int>? {
if (a.size < 2) return null
var sum: Int
for (i in 0..a.size - 2) {
if (a[i] <= targetSum) {
for (j in i + 1..a.size - 1) {
sum = a[i] + a[j]
if (sum == targetSum) return Pair(i, j)
if (sum > targetSum) break
}
} else {
break
}
}
return null
}
 
fun main(args: Array<String>) {
val a = intArrayOf(0, 2, 11, 19, 90)
val targetSum = 21
val p = twoSum(a, targetSum)
if (p == null) {
println("No two numbers were found whose sum is $targetSum")
} else {
println("The numbers with indices ${p.first} and ${p.second} sum to $targetSum")
}
}
Output:
The numbers with indices 1 and 3 sum to 21

Lua[edit]

Lua uses one-based indexing.

function twoSum (numbers, sum)
local i, j, s = 1, #numbers
while i < j do
s = numbers[i] + numbers[j]
if s == sum then
return {i, j}
elseif s < sum then
i = i + 1
else
j = j - 1
end
end
return {}
end
 
print(table.concat(twoSum({0,2,11,19,90}, 21), ","))
Output:
2,4

Nim[edit]

proc twoSum (src : openarray[int], target : int ) : array[2, int] =
if src.len < 2:
return
 
for base in 0 .. (src.len - 2):
for ext in (base + 1) .. < src.len:
if (src[base] + src[ext]) == target:
result[0] = base
result[1] = ext
 
 
proc main =
var data0 = [0, 2, 11, 19, 90]
var res = twoSum(data0, 21)
assert(res == [1, 3])
 
var data1 = [0, 2, 11, 19, 90]
res = twoSum(data1, 22)
assert(res == [0, 0])
 
var data2 = [1]
res = twoSum(data2, 22)
assert(res == [0, 0])
 
var data3 = [1, 99]
res = twoSum(data3, 100)
assert(res == [0, 1])
 
var data4 = [1, 99]
res = twoSum(data4, 101)
assert(res == [0, 0])
 
 
main()

ooRexx[edit]

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'
Output:
[1,3]

Pascal[edit]

A little bit lengthy. Implemented an unsorted Version with quadratic runtime too and an extra test case with 83667 elements that needs 83667*86666/2 ~ 3.5 billion checks ( ~1 cpu-cycles/check, only if data in cache ).

program twosum;
{$IFDEF FPC}{$MODE DELPHI}{$ELSE}{$APPTYPE CONSOLE}{$ENDIF}
uses
sysutils;
type
tSolRec = record
SolRecI,
SolRecJ : NativeInt;
end;
tMyArray = array of NativeInt;
const
// just a gag using unusual index limits
ConstArray :array[-17..-13] of NativeInt = (0, 2, 11, 19, 90);
 
function Check2SumUnSorted(const A :tMyArray;
sum:NativeInt;
var Sol:tSolRec):boolean;
//Check every possible sum A[max] + A[max-1..0]
//than A[max-1] + A[max-2..0] etc pp.
//quadratic runtime: maximal (max-1)*max/ 2 checks
//High(A) always checked for dynamic array, even const
//therefore run High(A) to low(A), which is always 0 for dynamic array
label
SolFound;
var
i,j,tmpSum: NativeInt;
Begin
Sol.SolRecI:=0;
Sol.SolRecJ:=0;
i := High(A);
while i > low(A) do
Begin
tmpSum := sum-A[i];
j := i-1;
while j >= low(A) do
begin
//Goto is bad, but fast...
if tmpSum = a[j] Then
GOTO SolFound;
dec(j);
end;
dec(i);
end;
result := false;
exit;
SolFound:
Sol.SolRecI:=j;Sol.SolRecJ:=i;
result := true;
end;
 
function Check2SumSorted(const A :tMyArray;
sum:NativeInt;
var Sol:tSolRec):boolean;
var
i,j,tmpSum: NativeInt;
Begin
Sol.SolRecI:=0;
Sol.SolRecJ:=0;
i := low(A);
j := High(A);
while(i < j) do
Begin
tmpSum := a[i] + a[j];
if tmpSum = sum then
Begin
Sol.SolRecI:=i;Sol.SolRecJ:=j;
result := true;
EXIT;
end;
if tmpSum < sum then
begin
inc(i);
continue;
end;
//if tmpSum > sum then
dec(j);
end;
writeln(i:10,j:10);
result := false;
end;
 
var
Sol :tSolRec;
CheckArr : tMyArray;
MySum,i : NativeInt;
 
Begin
randomize;
setlength(CheckArr,High(ConstArray)-Low(ConstArray)+1);
For i := High(CheckArr) downto low(CheckArr) do
CheckArr[i] := ConstArray[i+low(ConstArray)];
 
MySum := 21;
IF Check2SumSorted(CheckArr,MySum,Sol) then
writeln('[',Sol.SolRecI,',',Sol.SolRecJ,'] sum to ',MySum)
else
writeln('No solution found');
 
//now test a bigger sorted array..
setlength(CheckArr,83667);
For i := High(CheckArr) downto 0 do
CheckArr[i] := i;
MySum := CheckArr[Low(CheckArr)]+CheckArr[Low(CheckArr)+1];
writeln(#13#10,'Now checking array of ',length(CheckArr),
' elements',#13#10);
//runtime about 1 second
IF Check2SumUnSorted(CheckArr,MySum,Sol) then
writeln('[',Sol.SolRecI,',',Sol.SolRecJ,'] sum to ',MySum)
else
writeln('No solution found');
//runtime not measurable
IF Check2SumSorted(CheckArr,MySum,Sol) then
writeln('[',Sol.SolRecI,',',Sol.SolRecJ,'] sum to ',MySum)
else
writeln('No solution found');
end.
Output:
[1,3] sum to 21

Now checking array of 83667 elements

[0,1] sum to 1
[0,1] sum to 1

real    0m1.013s

Perl[edit]

Translation of: Python
 
sub two_sum{
my @arr = @{shift @_};
my $num = shift;
my $i = 0;
my $j = $#arr - 1;
while ($i < $j) {
if ($arr[$i] + $arr[$j] == $num) {
return ($i, $j);
}
if ($arr[$i] + $arr[$j] < $num) {
$i += 1;
}
else {
$j -= 1;
return;
}
}
}
 
 
my @numbers = (0, 2, 11, 19, 90);
my ($n1, $n2) = two_sum(\@numbers, 21);
print "$n1 $n2\n";
($n1, $n2) = two_sum(\@numbers, 25);
print "$n1 $n2\n";
 
 

Perl 6[edit]

Translation of: zkl
sub two_sum ( @numbers, $sum ) {
die '@numbers is not sorted' unless [<=] @numbers;
 
my ( $i, $j ) = 0, @numbers.end;
while $i < $j {
given $sum <=> @numbers[$i,$j].sum {
when Order::More { $i += 1 }
when Order::Less { $j -= 1 }
when Order::Same { return $i, $j }
}
}
return;
}
 
say two_sum ( 0, 2, 11, 19, 90 ), 21;
say two_sum ( 0, 2, 11, 19, 90 ), 25;
Output:
(1 3)
Nil

Phix[edit]

function twosum(sequence s, integer t)
for i=1 to length(s) do
for j=i+1 to length(s) do
if s[i]+s[j]=t then
return {i,j}
end if
end for
end for
return {}
end function
?twosum({0, 2, 11, 19, 90},21)
Translation of: Perl 6
function twosum(sequence numbers, integer total)
integer i=1, j=length(numbers)
while i<j do
switch compare(numbers[i]+numbers[j],total) do
case -1: i += 1
case 0: return {i, j}
case +1: j -= 1
end switch
end while
return {}
end function
Output:

Phix uses 1-based indexes

{2,4}

PicoLisp[edit]

(de twosum (Lst N)
(for ((I . A) Lst A (cdr A))
(T
(for ((J . B) (cdr Lst) B (cdr B))
(T (= N (+ (car A) (car B)))
(cons I (inc J)) ) )
@ ) ) )
(println
(twosum (0 2 11 19 90) 21)
(twosum (-3 -2 0 1 5 8 11) 17)
(twosum (-8 -2 -1 1 5 9 11) 0) )
Output:
(2 . 4) NIL (3 . 4)

PowerShell[edit]

Lazy, very lazy.

 
$numbers = @(0, 2, 11, 19, 90)
$sum = 21
 
$totals = for ($i = 0; $i -lt $numbers.Count; $i++)
{
for ($j = $numbers.Count-1; $j -ge 0; $j--)
{
[PSCustomObject]@{
FirstIndex = $i
SecondIndex = $j
TargetSum = $numbers[$i] + $numbers[$j]
}
}
}
 
$totals | Where-Object TargetSum -EQ $sum |
Select-Object -First 1 `
-Property @{
Name = "Sum"
Expression = { $_.TargetSum }
},
@{
Name = "Indices"
Expression = { @($_.FirstIndex, $_.SecondIndex) }
}
 
Output:
Sum Indices
--- -------
 21 {1, 3} 

Python[edit]

Translation of: Perl 6
 
def two_sum(arr, num):
i = 0
j = len(arr) - 1
while i < j:
if arr[i] + arr[j] == num:
return (i, j)
if arr[i] + arr[j] < num:
i += 1
else:
j -= 1
return None
 
 
numbers = [0, 2, 11, 19, 90]
print(two_sum(numbers, 21))
print(two_sum(numbers, 25))
 
 

Racket[edit]

#lang racket/base
(define (two-sum v m)
(let inr ((l 0) (r (sub1 (vector-length v))))
(and
(not (= l r))
(let ((s (+ (vector-ref v l) (vector-ref v r))))
(cond [(= s m) (list l r)] [(> s m) (inr l (sub1 r))] [else (inr (add1 l) r)])))))
 
(module+ test
(require rackunit)
 ;; test cases
 ;; no output indicates returns are as expected
(check-equal? (two-sum #( 0 2 11 19 90) 21) '(1 3))
(check-equal? (two-sum #(-8 -2 0 1 5 8 11) 3) '(0 6))
(check-equal? (two-sum #(-3 -2 0 1 5 8 11) 17) #f)
(check-equal? (two-sum #(-8 -2 -1 1 5 9 11) 0) '(2 3)))

REXX[edit]

version 1[edit]

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'
Output:
[1,3]

version 2[edit]

This REXX version uses optimization in using integers that take advantage that the numbers are an ordered list of positive integers.

All solutions are listed (if any).

This REXX solution makes allowances for the inclusion of zero, even though it is specifically excluded by the task's description.   However zero is included in the task's requirement.

If the list isn't an ordered list of positive integers, then the   while   clause (below) should be removed,   and then this REXX version will work with any list   (including negative numbers and also with any real number.

/*REXX pgm find 2 integers in a ordered list of positive integers that sum to a number. */
list=0 2 11 19 90 ; say 'order list: ' list " (using a zero index.)"
sum=21  ; say 'target sum: ' sum
 
do #=0 for words(list) while word(list, #+1)<=sum /*only use possibles.*/
@.#=word(list, #+1)
end /*#*/
say /* [↓] look for sum of 2 int = the sum*/
do a=0 for # /*scan up to the last possible integer.*/
do b=a+1 to #-1; if @.[email protected].b=sum then say 'a solution: ['a"," b']'
end /*y*/ /* [↑] 2 elements sum to target? Tell*/
end /*x*/ /*stick a fork in it, we're all done. */

output

order list:  0 2 11 19 90           (using a zero index.)
target sum:  21

a solution:  [1, 3]

Ring[edit]

 
# Project : Two Sum
# Date  : 2017/09/22
# Author  : Gal Zsolt (~ CalmoSoft ~)
# Email  : <[email protected]>
 
numbers = [0, 2, 11, 19, 90]
sum = 21
 
see "order list: "
for n=1 to len(numbers)
see " " + numbers[n]
next
see " (using a zero index.)" + nl
for n=1 to len(numbers)
for m=n to len(numbers)
if numbers[n] + numbers[m] = sum
see "target sum: " + sum + nl
see "a solution: ["
see "" + (n-1) + " " + (m-1) + "]" + nl
ok
next
next
 

Output:

order list:  0 2 11 19 90 (using a zero index.)
target sum:  21
a solution: [1 3]

Ruby[edit]

def two_sum(numbers, sum)
numbers.each_with_index do |x,i|
if j = numbers.index(sum - x) then return [i,j] end
end
[]
end
 
numbers = [0, 2, 11, 19, 90]
p two_sum(numbers, 21)
p two_sum(numbers, 25)
Output:
[1, 3]
[]

When the size of the Array is bigger, the following is more suitable.

def two_sum(numbers, sum)
numbers.each_with_index do |x,i|
key = sum - x
if j = numbers.bsearch_index{|y| key<=>y}
return [i,j]
end
end
[]
end

Sidef[edit]

Translation of: Perl 6
func two_sum(numbers, sum) {
var (i, j) = (0, numbers.end)
while (i < j) {
given (sum <=> numbers[i]+numbers[j]) {
when (-1) { --j }
when (+1) { ++i }
default { return [i, j] }
}
}
return []
}
 
say two_sum([0, 2, 11, 19, 90], 21)
say two_sum([0, 2, 11, 19, 90], 25)
Output:
[1, 3]
[]

VBA[edit]

Option Explicit
Function two_sum(a As Variant, t As Integer) As Variant
Dim i, j As Integer
i = 0
j = UBound(a)
Do While (i < j)
If (a(i) + a(j) = t) Then
two_sum = Array(i, j)
Exit Function
ElseIf (a(i) + a(j) < t) Then i = i + 1
ElseIf (a(i) + a(j) > t) Then j = j - 1
End If
Loop
two_sum = Array()
End Function
Sub prnt(a As Variant)
If UBound(a) = 1 Then
Selection.TypeText Text:="(" & a(0) & ", " & a(1) & ")" & vbCrLf
Else
Selection.TypeText Text:="()" & vbCrLf
End If
End Sub
Sub main()
Call prnt(two_sum(Array(0, 2, 11, 19, 90), 21))
Call prnt(two_sum(Array(-8, -2, 0, 1, 5, 8, 11), 3))
Call prnt(two_sum(Array(-3, -2, 0, 1, 5, 8, 11), 17))
Call prnt(two_sum(Array(-8, -2, -1, 1, 5, 9, 11), 0))
End Sub
Output:
(1, 3)
(0, 6)
()
(2, 3)

zkl[edit]

The sorted O(n) no external storage solution:

fcn twoSum(sum,ns){
i,j:=0,ns.len()-1;
while(i<j){
if((s:=ns[i] + ns[j]) == sum) return(i,j);
else if(s<sum) i+=1;
else if(s>sum) j-=1;
}
}
twoSum2(21,T(0,2,11,19,90)).println();
twoSum2(25,T(0,2,11,19,90)).println();
Output:
L(1,3)
False

The unsorted O(n!) all solutions solution:

fcn twoSum2(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)) })
}
twoSum2(21,T(0,2,11,19,90,21)).println();
twoSum2(25,T(0,2,11,19,90,21)).println();
Output:
L(L(0,5),L(1,3))
L()