-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathFind triplets with zero sum(google).java
83 lines (73 loc) · 1.69 KB
/
Find triplets with zero sum(google).java
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/*
Given an array A[] of n elements.
The task is to complete the function which returns true if triplets exists in array A[] whose sum is zero else returns false.
Example(To be used only for expected output) :
Input:
2
5
0 -1 2 -3 1
3
1 2 3
Output:
1
0
*/
/*Please note that it's Function problem i.e.
you need to write your solution in the form of Function(s) only.
Driver Code to call/invoke your function is mentioned above.*/
/*Complete the function below*/
class GfG
{
public boolean findTriplets(int arr[] , int n)
{
//add code here.
Arrays.sort(arr);
boolean found = false;
for (int i=0;i<n&&found==false;i++){
int l = i+1,r = n-1;
while (l<r){
int curSum = arr[i]+arr[l]+arr[r];
if (curSum==0){
//System.out.println("1");
found = true;
break;
}
else if (curSum>0){
r--;
}
else {
l++;
}
}
}
return found;
}
}
second method :-
class GfG
{
public boolean findTriplets(int arr[] , int n)
{
Arrays.sort(arr);
int count = 0;
// -3 -2 -1 1 2 3
for (int j = 0; j <= n - 2; j++) {
int a = j + 1;
int b = n - 1;
while (a < b) {
if (arr[a] + arr[b] == -arr[j]) {
count++;
break;
// a++;
// b--;
} else if (arr[a] + arr[b] < -arr[j]) {
a++;
} else {
b--;
}
}
}
return count > 0 ? true:false;
}
}
//Time Complexity: O(n^2)