3 sum algorithm - Trying

Question

Recently I started looking and refreshing about algorithms and decided to try to do the 3 sum algorithm. I did the code below:

public static int[] tripletSum(int[] A, int sum) {
 HashMap<Integer, Boolean> data = new HashMap<>();
 for (int i = 0; i < A.length; i++) {
 data.put(A[i], true);
 }
 int i = 0;
 int j = 1;
 while (i < A.length && j < A.length) {
 Integer a = A[i];
 Integer b = A[j];
 Integer delta = sum - (a + b);
 if (data.containsKey(delta) && a != delta && b != delta && (a + b + delta) == sum) {
 int[] result = {a, b, delta};
 return result;
 }
 i++;
 j++;
 }
 return null;
}

I'd like opinions about if it is good logic, time complexity, improvements. Any tips and comments will be great.

The piece of code below:

if (data.containsKey(remainder) && a != remainder && b != remainder && (a + b + remainder) == sum) {

is included to avoid to repeat values in a and b, and to guarantee the sum result as expected.

Thanks

• konijn: This 3sum algorithm: en.wikipedia.org/wiki/3SUM ?
• Edson Martins: I hope yes. A long time ago in a technical interview asked me to create an algorithm used to find three values in an array where the sum equals a sum parameter, like [5,1,2,1,8] and the sum expected is 15, interact in the loop finding the values where the sum equals 15.

Answer 1

According to the comment by @konijn and your answer to his comment below your question you tried to implement a variant of the algorithm 3SUM but your implementation is totally wrong.

Let's start again: given an array and a value k you want to find three elements a, b, c in the array that satisfy the condition a + b + c = k. To obtain a complexity of O(n2) you have to use an hashtable to store values already checked in the array so if you have a and b and the hashtable contains the value c = k - (a + b) the algorithm ends. In this case instead of an hashtable I will use an hashset like I explain later. The initial implementation of your method will be like this:

public static int[] tripletSum(int[] arr, int k) { 
 final int n = arr.length;
 if (n < 3) { return null; }
 int[] numbers = Arrays.copyOf(arr, n);
 Arrays.sort(numbers);
 ...omitted
}

You have chosen to return the triplet (a, b, c) if a + b + c = k, otherwise you return the null triplet if the length of the array if less than 3 or none triplet (a, b, c) satisfies the sum condition a + b + c = k. Now add the logic of algorithm to the body of method like below:

public static int[] tripletSum(int[] arr, int k) { 
 final int n = arr.length;
 if (n < 3) { return null; }
 int[] numbers = Arrays.copyOf(arr, n);
 Arrays.sort(numbers);
 for (int i = 0; i < n - 1; ++i) {
 if (i > 0 && numbers[i] == numbers[i - 1]) { continue; } 
 Set<Integer> set = new HashSet<>();
 int a = numbers[i];
 for (int j = i + 1; j < n; ++j) {
 int b = numbers[j];
 int c = k - (a + b);
 if (set.contains(c)) {
 return new int[] {a, b, c};
 }
 set.add(b);
 }
 }
 return null;
}

I made a copy of the original array and sorted it so all duplicate numbers are consecutive : in this way in the loop once for a number a the there are no b and c that satisfy the condition a + b + c = k, the loop ignore all equal numbers to n with instruction continue.

I use the HashSet to store the c values, so in every cycle of the loop I have a and b and I check if the hashset contains the value c = k - (a + b). If yes, the function returns the triplet (a, b, c) otherwise the value b is stored in the hashset if not already present as a c value for next iterations.

Answer 2

There is no reason to use HashMap, you are not using the bools anywhere. So I think You could just use HashSet. Which you don't need to feed in foreach, instead simply pass the integers as constructor parameter.

var set = new HashSet(A);

You don't have to compare both i and j

i < A.length && j < A.length

if j is always one larger then i, just compare with j.

This condition is always true:

(a + b + delta) == sum

since that is the way it was obtained in the first place:

Integer delta = sum - (a + b);

This:

int[] result = {a, b, delta};
return result;

could be just

return {a, b, delta};

You are returning null where you claim to return int[], not sure if that's correct.

Anyway I think your implementation does not work as intended, because it only looks for sums of two consecutive and third anywhere. It fails for example on [5,1,2,1,8] looking for 15=5+2+8.

• Edson Martins: Thanks @slepic, but I tried using the [5,1,2,1,8], and got the result 5 2 8. If I get the sum result expected less every 2 elements from the array, the result will be a key found in the Hash. For example: If the array is [5,1,2,1,8] and looking to find three values inside where is the sum is equal to 15, when interacting in the loop I'll get the first and second element(A[0] and A[1]), 1 + 2 (array sorted) and 15 - 3 = 12. Is it 12 a key? not. Now we'll interact again, and so on :-)
• slepic: @EdsonMartins hehe ok I guess I will have to actually run it :)
• Edson Martins: Thanks again @slepic, I changed to HashSet, the loop with j variable, etc Perfectly heheh.
• slepic: @EdsonMartins well, first I realized this is not C# as I thought :D But nevertheless with only few little changes it works in C# too :) Anyway it does not find solution for [5,1,2,1,8]=15, but it finds it for [5,1,2,8]=15. And going through the code logicaly leads me to conclusion that this should be the case in java as well, as I already wrote in my answer. I understand how you implemented it and that exactly makes me think it should not find solution [5,1,2,1,8]=15. No idea how it did, unless you changed the code already..
• slepic: @EdsonMartins cause 15-(5+1)=9 -> not in the set; 15-(1+2)=12 -> not in the set; 15-(2+1)=12 -> not in the set; 15-(1+8)=6 -> not in the set; the end.