j2emanue j2emanue - 6 months ago 7
Java Question

find if 3 numbers in an array add up to a sum

I have a method written to determine if a sum exists in an array. So the rule is there must exist 3 numbers in the array such that adding them all together equals to a given sum. So in the array {1,2,3,14,12} if i was searching for a sum of 6 then 2+3+1 would be the numbers that give me 6. From researching online this can be done with a set so i have the following function which works but im having a hard time understanding the logic:

public void existsSum(int[] numbers,int sum){

Set<Integer> set = new HashSet();

for(int i=0;i<numbers.length;i++){
int s1=sum - numbers[i];
for(int j=0;j<numbers.length;j++){
int s2=s1-numbers[j];
if(set.contains(s2)) {
System.out.format("sum of %d + %d + %d gives %d \n", numbers[i], numbers[j],s2, sum);
assert(numbers[i]+numbers[j]+s2==10);
}
}
set.add(numbers[i]);

}
}


I dont understand what is the significance of s1 and s2 ? can someone explain to me the logic. The method itself works fine and if i run it with the following it yields the correct results:

int[] integers = {1,2,3,4,5,6,7,8,9};

existsSum(integers,10);


sum of 2 + 7 + 1 gives 10
sum of 3 + 5 + 2 gives 10
sum of 3 + 6 + 1 gives 10
sum of 4 + 3 + 3 gives 10
sum of 4 + 4 + 2 gives 10
sum of 4 + 5 + 1 gives 10
sum of 5 + 1 + 4 gives 10
sum of 5 + 2 + 3 gives 10
sum of 5 + 3 + 2 gives 10
sum of 5 + 4 + 1 gives 10
sum of 6 + 1 + 3 gives 10
sum of 6 + 2 + 2 gives 10
sum of 6 + 3 + 1 gives 10
sum of 7 + 1 + 2 gives 10
sum of 7 + 2 + 1 gives 10
sum of 8 + 1 + 1 gives 10

Answer

Your code doesn't work, because i and j may point to the same number.
Also, the assert hardcodes the sum to find as 10.

Anyway, the main logic without set is 3 nested loops:

  • Loop 1: Loop thru all numbers.
  • Loop 2: Loop thru all numbers following current number from loop 1.
  • Loop 3: Loop thru all numbers following current number from loop 2.
  • If sum of the 3 current numbers is correct, print it.
for (int i = 0; i < numbers.length; i++)
    for (int j = i + 1; j < numbers.length; j++)
        for (int k = j + 1; k < numbers.length; k++)
            if (numbers[i] + numbers[j] + numbers[k] == sum)
                System.out.println("sum of %d + %d + %d gives %d\n",
                                   numbers[i], numbers[j], numbers[k], sum);

For performance improvement, the innermost loop can be optimized, by instead calculating the 3rd number as num3 = sum - num1 - num2, then see if it is in the list of numbers.

To prevent using the same number more than once, the logic of the 3rd check is reversed to check against all numbers preceding the current number from loop 1, and to build the set of such numbers as the first list is iterated.

Pseudo-code:

set = new set()
for (int i = 0; i < numbers.length; i++)
    for (int j = i + 1; j < numbers.length; j++) {
        num3 = sum - numbers[i] - numbers[j]
        if (num3 in set)
            print("sum of %d + %d + %d gives %d\n",
                  num3, numbers[i], numbers[j], sum);
    }
    add numbers[i] to set
}
Comments