资源简介
算法4谢路云源码之ThreeSumFast,快速计算三数之和,供大家参考使用,
代码片段和文件信息
/******************************************************************************
* 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.
*
评论
共有 条评论