st0le
6/30/2013 - 1:47 AM

3SUM Solution : O(n^2) algorithm with Hash Table

3SUM Solution : O(n^2) algorithm with Hash Table


    // Complexity - O(n^2), Space Complexity - O(n^2)
    private int[] findTriple_3(int[] A) {
        Map<Integer, int[]> map = new HashMap<Integer, int[]>();
        for (int i = 0, l = A.length; i < l; i++) {
            map.clear();
            for (int j = i + 1; j < l; j++) {
                if (map.containsKey(A[j])) {
                    int[] pair = map.get(A[j]);
                    return new int[]{pair[0], pair[1], A[j]};
                } else
                    map.put(-A[i] - A[j], new int[]{A[i], A[j]});
            }
        }
        return null;
    }