TripletSUm.java

import java.util.*;
public class Solution {	

	public static int tripletSum(int[] A, int num) {
		Arrays.sort(A);// nlog(n)
        int len = A.length;
        int count = 0;
        for(int i=0; i<len; i++) {
            int pairsum=num -A[i];
            count+=getPairsCount(A,i+1, len-1,pairsum);
        }
        return count;
	}
    
    static int getPairsCount(int[] A, int st, int end, int sum) {
        int count = 0;
        while(st<end) {
            if(A[st]+A[end]==sum) {
                if(A[st]==A[end]){
                    int total = end-st+1;
                    count+=(total*(total-1))/2;
                    return count;
                }
                int si=st+1;
                int ei=end-1;
                while(si<=ei && A[st]==A[si]){si++; }
                while (ei >= si && A[end] == A[ei]) {
                    ei--;
                }
                count+=((si-st)*(end-ei));
                st=si;end=ei;
            }else if(A[st]+A[end]<sum) st++;
            else end--;
        }

        return count;
    }
}