Two sum: Difference between revisions

Content added Content deleted

Inline

@@ Line 80: / Line 80: @@
 =={{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){
+   m:=ns.len()/2;
-   Utils.Helpers.combosKW(2,ns).filter('wrap([(a,b)]){ a+b==sum })  // lazy combos
+   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)) })
+      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>
+{{out}}
+<pre>
+L(1,3)
+False
+</pre>
+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
-   rs:=List();
-   foreach i,j in (ns.len(),i){
+   .apply('wrap([(a,b)]){ return(ns.index(a),ns.index(b)) })
-      if(ns[i] + ns[j] == sum) rs.append(T(i,j));
-   }
-   rs
 }</lang>
-<lang zkl>twoSum(21,T(0,2,11,19,21,90)).println();
+<lang zkl>twoSum2(21,T(0,2,11,19,21,90)).println();
-twoSum(25,T(0,2,11,19,21,90)).println();</lang>
+twoSum2(25,T(0,2,11,19,21,90)).println();</lang>
 {{out}}
 <pre>