Given an array of sorted integers, how can I find if there exists a set of 3 elements that sum to K? [duplicate]

Question

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.

Answer 1

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;
        }
    }

Answer 2

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.