package com.interview.array;

import java.util.Arrays;

/**
 * http://www.geeksforgeeks.org/find-a-triplet-that-sum-to-a-given-value/
 */
public class TripletInArray {

    class Triplet {
        int a;
        int b;
        int c;

        public String toString() {
            return a + " " + b + " " + c;
        }
    }

    public Triplet findTriplet(int input[], int sum) {
        Arrays.sort(input);
        for (int i = 0; i < input.length - 2; i++) {

            int start = i + 1;
            int end = input.length - 1;
            int new_sum = sum - input[i];
            while (start < end) {
                if (new_sum == input[start] + input[end]) {
                    Triplet t = new Triplet();
                    t.a = input[i];
                    t.b = input[start];
                    t.c = input[end];
                    return t;
                }
                if (new_sum > input[start] + input[end]) {
                    start++;
                } else {
                    end--;
                }
            }
        }
        return null;
    }

    public static void main(String args[]){
        TripletInArray tip = new TripletInArray();
        int input[] = {1,2,6,9,11,18,26,28};
        int sum = 22;
        System.out.println(tip.findTriplet(input, sum));
    }
}

@@ -45,17 +45,68 @@
 il.Array
-s
+List;%0Aimport java.util.Arrays;%0Aimport java.util.List
 ;%0A%0A/**%0A 
@@ -1100,32 +1100,32 @@
     %7D%0A        %7D%0A
-
         return n
@@ -1128,32 +1128,1276 @@
 rn null;%0A    %7D%0A%0A
+    /**%0A     * https://leetcode.com/problems/3sum/%0A     */%0A    public List%3CList%3CInteger%3E%3E threeSum(int%5B%5D nums) %7B%0A        Arrays.sort(nums);%0A        List%3CList%3CInteger%3E%3E result = new ArrayList%3C%3E();%0A        for (int i = 0; i %3C nums.length - 2; i++) %7B%0A            if (i != 0 && nums%5Bi%5D == nums%5Bi-1%5D) %7B%0A                continue;%0A            %7D%0A            int start = i + 1;%0A            int end = nums.length - 1;%0A            while (start %3C end) %7B%0A                if (nums%5Bi%5D + nums%5Bstart%5D + nums%5Bend%5D == 0) %7B%0A                    List%3CInteger%3E r = new ArrayList%3C%3E();%0A                    r.add(nums%5Bi%5D);%0A                    r.add(nums%5Bstart%5D);%0A                    r.add(nums%5Bend%5D);%0A                    result.add(r);%0A                    start++;%0A                    end--;%0A                    while(start %3C nums.length && nums%5Bstart%5D == nums%5Bstart - 1%5D) %7B%0A                        start++;%0A                    %7D%0A                    while(end %3E= 0 && nums%5Bend%5D == nums%5Bend+1%5D) %7B%0A                        end--;%0A                    %7D%0A                %7D else if (nums%5Bi%5D + nums%5Bstart%5D + nums%5Bend%5D %3C 0) %7B%0A                    start++;%0A                %7D else %7B%0A                    end--;%0A                %7D%0A            %7D%0A        %7D%0A        return result;%0A    %7D%0A%0A
     public stati

triplet sum to 0