So say I have a sorted array:
{ 1, 2, 3, 4, 5, 6 }
And I want to see if there exists three elements that sum to 14.
3 + 5 + 6 = 14
I'm pretty sure there is no way to do this in O(N) time, but I think it can be done in O(N^2) somehow.
Algorithm: Given an array of length n and a sum s. Create three nested loop first loop runs from start to end (loop counter i), second loop runs from i+1 to end (loop counter j) and third loop runs from j+1 to end (loop counter k) The counter of these loops represents the index of 3 elements of the triplets.
A simple solution is to first find intersection of two arrays and store the intersection in a temporary array, then find the intersection of third array and temporary array. Time complexity of this solution is O(n1 + n2 + n3) where n1, n2 and n3 are sizes of ar1[], ar2[] and ar3[] respectively.
This problem is similar to the 3SUM problem and it can done in O(N^2)
. This java working code accomplishes this.
// The function prints the values if there exists 3 distinct indices
// in the array arr that sum to req.
void run(){
int[] arr = { 1, 2, 3, 4, 5, 6 };
int req = 14;
// For the algorithm to work correctly, the array must be sorted
Arrays.sort(arr);
for(int i=0; i<arr.length; i++){// Iterate over the elements of the array.
// Check in linear time whether there exists distinct indices
// lo and hi that sum to req-arr[i]
int lo=0, hi = arr.length-1;
boolean found = false;
while(lo<hi){
if(lo==i){
lo++;
continue;
}
if(hi==i){
hi--;
continue;
}
int val = arr[lo] + arr[hi] + arr[i];
if(val == req){
System.out.println(arr[lo] + " + " + arr[hi] + " + " + arr[i] + " = " + req);
found = true;
break;
}else if(val < req){
lo++;
}else{
hi--;
}
}
if(found)break;
}
}
In Computational theory, this is known as 3sum problem. Best solution for this problem found so far costs O(N^2). It is still an open question whether this can be solved with better cost. You can find one implementation of this algorithm here.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With