Package org.drip.graph.subarray

Class ThreeSumQuadraticHash

java.lang.Object
org.drip.graph.subarray.ThreeSum
org.drip.graph.subarray.ThreeSumQuadraticHash
public class ThreeSumQuadraticHash
extends ThreeSum
ThreeSumQuadraticHash implements the Check that indicates if the Set of Numbers contains 3 that Sum to Zero using a Hash-table, leading to a Quadratic Time Algorithm. The References are:

  • Chan, T. M. (2018): More Logarithmic Factor Speedups for 3SUM, (median+) Convolution, and some Geometric 3SUM-Hard Problems Proceedings of the 29th Annual ACM SIAM Symposium on Discrete Algorithms 881-897
  • Gajentaan, A., and M. H. Overmars (1995): On a Class of O(n2) Problems in Computational Geometry Computational Geometry: Theory and Applications 5 (3) 165-185
  • Kopelowitz, T., S. Pettie, and E. Porat (2014): Higher Lower Bounds from the 3SUM Conjecture https://arxiv.org/abs/1407.6756 arXiV
  • Patrascu, M. (2010): Towards Polynomial Lower Bounds for Dynamic Problems Proceedings of the 42nd ACM Symposium on Theory of Computing 603-610
  • Wikipedia (2020): 3Sum https://en.wikipedia.org/wiki/3SUM




Author:
Lakshmi Krishnamurthy

  • Constructor Summary

    Constructors
    Constructor Description
    ThreeSumQuadraticHash​(double[] numberArray)
    ThreeSumQuadraticHash Constructor

  • Method Summary

    Modifier and Type Method Description
    boolean zeroSumExists()
    Indicate if the Zero Sum Match exists

    Methods inherited from class org.drip.graph.subarray.ThreeSum

    numberArray

    Methods inherited from class java.lang.Object

    equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • ThreeSumQuadraticHash

      public ThreeSumQuadraticHash​(double[] numberArray) throws java.lang.Exception
      ThreeSumQuadraticHash Constructor
      Parameters:
      numberArray - The Number Array
      Throws:
      java.lang.Exception - Thrown if the Inputs are Invalid

  • Method Details

    • zeroSumExists

      public boolean zeroSumExists()
      Description copied from class: ThreeSum
      Indicate if the Zero Sum Match exists
      Specified by:
      zeroSumExists in class ThreeSum
      Returns:
      TRUE - The Zero Sum Match exists