Three Set Sum: Given an integer k and 3 sets A, B and C, find a, b, c such that a + b + c = k

0 votes

You are given an integer k and 3 sets A, B and C, each containing n numbers.  Give an efficient algorithm to determine if there exist 3 integers a, b, c (in sets A, B, C respectively), such that a + b + c = k.  The time complexity of your algorithm should be O(n2) or better.

asked Jul 23 in Divide & Conquer by Amrinder Arora (206 points)

1 Answer

+1 vote

1.Add each two values of the first two arrays and insert the value into a map. O(n^2).

2.Find if there is a value in the third array matches with the map.O(2n).

Code:

public void findvalue(int[] a,int[] b,int[] c,int value){
    Map<Integer,Integer> map = new HashMap<>();
    for (int i=0;i<a.length;i++){
        for (int j=0;j<b.length;j++){
            int sum = a[i]+b[j];
            map.put(sum, 1);
        }
    }

    int result = 0;

    for (int i=0;i<c.length;i++){
        int define = map.getOrDefault(value-c[i], 0);
        if (define==1) {
            result = 1;
            break;
        }
    }

    if (result == 1) {
        System.out.println("There exist such triple numbers.");
    } else {
        System.out.println("No such triple numbers be found.");
    }
}

The time complexity would be O(n^2).

answered Aug 11 by jiahe0510 (128 points)
edited Aug 11 by jiahe0510
The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc
...