Repository navigation
Expand file tree
/
Copy pathThreeNumberSum.java
More file actions
57 lines (45 loc) · 1.52 KB
/
Copy pathThreeNumberSum.java
File metadata and controls
57 lines (45 loc) · 1.52 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
package com.java.sks.array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* @author sandeepsingh
*/
public class ThreeNumberSum {
/**
*
* @param array
* @param targetSum
* @return
* Given an array and targetSum find all posible combination of 3 digits which produce target sum.
* Time complexity is nLog(n) since we are sorting the array
*/
static List<Integer[]> threeNumberSum(int[] array, int targetSum) {
Arrays.sort(array);
List<Integer[]> integersList = new ArrayList<>();
for (int i = 0; i < array.length - 2; i++) {
int left = i + 1;
int right = array.length - 1;
while (left < right) {
int currentSum = array[i] + array[left] + array[right];
if (currentSum == targetSum) {
Integer[] temArray = {array[i], array[left], array[right]};
integersList.add(temArray);
left++;
right--;
} else if (currentSum < targetSum) {
left++;
} else if (currentSum > targetSum) {
right--;
}
}
}
return integersList;
}
public static void main(String[] args) {
int A[] = {1, 4, 45, 6, 10, 8};
int sum = 22;
List<Integer[]> finalList = threeNumberSum(A, sum);
Arrays.stream(finalList.iterator().next()).forEach(it -> System.out.println(it));
}
}