Revisions to Finding three elements in an array whose sum is closest to a given number

added 7 characters in body

edited Mar 18, 2014 at 19:11

313.3k
49
348
362

for (i in 1..n-2) { j = ii+1 // Start whereright iafter isi. k = n  // Start at the end of the array. while (k >= j) { // We got a match! All done. if (A[i] + A[j] + A[k] == 0) return (A[i], A[j], A[k]) // We didn't match. Let's try to get a little closer: // If the sum was too big, decrement k. // If the sum was too small, increment j. (A[i] + A[j] + A[k] > 0) ? k-- : j++ } // When the while-loop finishes, j and k have passed each other and there's // no more useful combinations that we can try with this i. }

for (i in 1..n-2) { j = i // Start where i is. k = n // Start at the end of the array. while (k >= j) { // We got a match! All done. if (A[i] + A[j] + A[k] == 0) return (A[i], A[j], A[k]) // We didn't match. Let's try to get a little closer: // If the sum was too big, decrement k. // If the sum was too small, increment j. (A[i] + A[j] + A[k] > 0) ? k-- : j++ } // When the while-loop finishes, j and k have passed each other and there's // no more useful combinations that we can try with this i. }

for (i in 1..n-2) { j = i+1 // Start right after i. k = n  // Start at the end of the array. while (k >= j) { // We got a match! All done. if (A[i] + A[j] + A[k] == 0) return (A[i], A[j], A[k]) // We didn't match. Let's try to get a little closer: // If the sum was too big, decrement k. // If the sum was too small, increment j. (A[i] + A[j] + A[k] > 0) ? k-- : j++ } // When the while-loop finishes, j and k have passed each other and there's // no more useful combinations that we can try with this i. }

edited pseudo code

Source Link

edited May 14, 2012 at 11:26

Zak

7.1k
6
39
54

for (i in 1..n-2) { j = i // Start where i is. k = n // Start at the end of the array. while (k >= j) { // We got a match! All done. return (A[i], A[j], A[k]) if (A[i] + A[j] + A[k] == 0) return (A[i], A[j], A[k]) // We didn't match. Let's try to get a little closer: // If the sum was too big, decrement k. // If the sum was too small, increment j. (A[i] + A[j] + A[k] > 0) ? k-- : j++ } // When the while-loop finishes, j and k have passed each other and there's // no more useful combinations that we can try with this i. }

for (i in 1..n-2) { j = i // Start where i is. k = n // Start at the end of the array. while (k >= j) { // We got a match! All done. return (A[i], A[j], A[k]) if (A[i] + A[j] + A[k] == 0) // We didn't match. Let's try to get a little closer: // If the sum was too big, decrement k. // If the sum was too small, increment j. (A[i] + A[j] + A[k] > 0) ? k-- : j++ } // When the while-loop finishes, j and k have passed each other and there's // no more useful combinations that we can try with this i. }

for (i in 1..n-2) { j = i // Start where i is. k = n // Start at the end of the array. while (k >= j) { // We got a match! All done. if (A[i] + A[j] + A[k] == 0) return (A[i], A[j], A[k]) // We didn't match. Let's try to get a little closer: // If the sum was too big, decrement k. // If the sum was too small, increment j. (A[i] + A[j] + A[k] > 0) ? k-- : j++ } // When the while-loop finishes, j and k have passed each other and there's // no more useful combinations that we can try with this i. }

corrected S to S/3 (consistent with comments)

Source Link

edit approved Jul 4, 2011 at 21:09

Jirka

4.2k
32
40

Notice that you can go from this version of the problem P' from P by subtracting your target valueS/3 from each element in A, but now you don't need the target value anymore.

Notice that you can go from this version of the problem P' from P by subtracting your target value from each element in A, but now you don't need the target value anymore.

Notice that you can go from this version of the problem P' from P by subtracting your S/3 from each element in A, but now you don't need the target value anymore.