/******************************************************************************
?*??Compilation:??javac?ThreeSumFast.java
?*??Execution:????java?ThreeSumFast?input.txt
?*??Dependencies:?StdOut.java?In.java?Stopwatch.java
?*??Data?files:???https://algs4.cs.princeton.edu/14analysis/1Kints.txt
?*????????????????https://algs4.cs.princeton.edu/14analysis/2Kints.txt
?*????????????????https://algs4.cs.princeton.edu/14analysis/4Kints.txt
?*????????????????https://algs4.cs.princeton.edu/14analysis/8Kints.txt
?*????????????????https://algs4.cs.princeton.edu/14analysis/16Kints.txt
?*????????????????https://algs4.cs.princeton.edu/14analysis/32Kints.txt
?*????????????????https://algs4.cs.princeton.edu/14analysis/1Mints.txt
?*
?*??A?program?with?n^2?log?n?running?time.?Reads?n?integers
?*??and?counts?the?number?of?triples?that?sum?to?exactly?0.
?*
?*??Limitations
?*??-----------
?*?????-?we?ignore?integer?overflow
?*?????-?doesn‘t?handle?case?when?input?has?duplicates
?*
?*
?*??%?java?ThreeSumFast?1Kints.txt
?*??70
?*??
?*??%?java?ThreeSumFast?2Kints.txt
?*??528
?*????????????????
?*??%?java?ThreeSumFast?4Kints.txt
?*??4039
?*?
?*??%?java?ThreeSumFast?8Kints.txt
?*??32074
?*
?*??%?java?ThreeSumFast?16Kints.txt
?*??255181
?*
?*??%?java?ThreeSumFast?32Kints.txt
?*??2052358
?*
?******************************************************************************/

package?edu.princeton.cs.algs4;

import?java.util.Arrays;

/**
?*??The?{@code?ThreeSumFast}?class?provides?static?methods?for?counting
?*??and?printing?the?number?of?triples?in?an?array?of?distinct?integers?that
?*??sum?to?0?（ignoring?integer?overflow）.
?*??

?*??This?implementation?uses?sorting?and?binary?search?and?takes?time?
?*??proportional?to?n^2?log?n?where?n?is?the?number?of?integers.
?*??

?*??For?additional?documentation?see?Section?1.4?of
?*??Algorithms?4th?Edition?by?Robert?Sedgewick?and?Kevin?Wayne.
?*
?*??@author?Robert?Sedgewick
?*??@author?Kevin?Wayne
?*/
public?class?ThreeSumFast?{

????//?Do?not?instantiate.
????private?ThreeSumFast（）?{?}

????//?returns?true?if?the?sorted?array?a[]?contains?any?duplicated?integers
????private?static?boolean?containsDuplicates（int[]?a）?{
????????for?（int?i?=?1;?i?????????????if?（a[i]?==?a[i-1]）?return?true;
????????return?false;
????}

????/**
?????*?Prints?to?standard?output?the?（i?j?k）?with?{@code?i??????*?such?that?{@code?a[i]?+?a[j]?+?a[k]?==?0}.
?????*
?????*?@param?a?the?array?of?integers
?????*?@throws?IllegalArgumentException?if?the?array?contains?duplicate?integers
?????*/
????public?static?void?printAll（int[]?a）?{
????????int?n?=?a.length;
????????Arrays.sort（