Two sum: Difference between revisions
(→{{header|zkl}}: sort arrays) |
(→{{header|zkl}}: re factor) |
||
Line 80: | Line 80: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
The sorted O(n) no external storage solution: |
|||
I think this is O(n!), The double loop solution is O(n^2). These two solutions don't care if the array is sorted |
|||
<lang zkl>fcn twoSum(sum,ns){ |
<lang zkl>fcn twoSum(sum,ns){ |
||
⚫ | |||
⚫ | |||
foreach i,j in (m,[ns.len()-1..m,-1]){ // make sure to see middle number |
|||
.apply('wrap([(a,b)]){ return(ns.index(a),ns.index(b)) }) |
|||
⚫ | |||
⚫ | |||
}</lang> |
}</lang> |
||
<lang zkl>twoSum2(21,T(0,2,11,19,21,90)).println(); |
|||
twoSum2(25,T(0,2,11,19,21,90)).println();</lang> |
|||
{{out}} |
|||
<pre> |
|||
L(1,3) |
|||
False |
|||
</pre> |
|||
The unsorted O(n!) all solutions solution: |
|||
<lang zkl>fcn twoSum2(sum,ns){ |
<lang zkl>fcn twoSum2(sum,ns){ |
||
⚫ | |||
⚫ | |||
.apply('wrap([(a,b)]){ return(ns.index(a),ns.index(b)) }) |
|||
⚫ | |||
⚫ | |||
rs |
|||
}</lang> |
}</lang> |
||
<lang zkl> |
<lang zkl>twoSum2(21,T(0,2,11,19,21,90)).println(); |
||
twoSum2(25,T(0,2,11,19,21,90)).println();</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
Revision as of 17:25, 4 October 2016
- 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
The sorted O(n) no external storage solution: <lang zkl>fcn twoSum(sum,ns){
m:=ns.len()/2; foreach i,j in (m,[ns.len()-1..m,-1]){ // make sure to see middle number if(ns[i] + ns[j] == sum) return(i,j); }
}</lang> <lang zkl>twoSum2(21,T(0,2,11,19,21,90)).println(); twoSum2(25,T(0,2,11,19,21,90)).println();</lang>
- Output:
L(1,3) False
The unsorted O(n!) all solutions solution: <lang zkl>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)) })
}</lang> <lang zkl>twoSum2(21,T(0,2,11,19,21,90)).println(); twoSum2(25,T(0,2,11,19,21,90)).println();</lang>
- Output:
L(L(0,4),L(1,3)) L()