forked from harshitbansal373/hacktoberfest2020
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Basics of Two pointers
47 lines (38 loc) · 1.15 KB
/
Basics of Two pointers
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
import java.util.Arrays;
//! amortized anaylysis - analyzes algo whose operations has varying T.C
//! two-pointers
//! basic idea of 2pointers - choose a subarray, with l and r
//! move l once right and move r until x is found or their sum of l~r is < x
//! if sum is found - break
//! else repeat
public class SubArraySum {
public static void main(String[] args) {
int arr[] = { 1, 3, 2, 5, 1, 1, 2, 3 };
int x = 3;
// * take subarray from l to r
// * inc l one step
int l = -1;
int r = 2;
while (l < arr.length) {
l++;
while ((sumlr(Arrays.copyOfRange(arr, l, r + 1))) < x && r < arr.length) {
r++;
}
if (sumlr(Arrays.copyOfRange(arr, l, r + 1)) == x) {
System.out.println("found @: " + l + ", " + r);
System.exit(0);
} else
continue;
}
System.out.println("Not found");
}
static int sumlr(int arr[]) {
int i = 0;
int sum = 0;
while (i < arr.length) {
sum += arr[i];
i++;
}
return sum;
}
}