leetcode/ArithmeticSlicesII-Subsequence/arithmetic_slices_II_subsequence.go at main · ayoubzulfiqar/leetcode · GitHub

Name: leetcode/ArithmeticSlicesII-Subsequence/arithmetic_slices_II_subsequence.go at main · ayoubzulfiqar/leetcode · GitHub
Rating: 4.9 (8750 reviews)
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
package main

import"math"

// func numberOfArithmeticSlices(nums []int) int {
// dic := map[[2]int]int{}
// var dfs func(int, int, int, []int, int) int
// dfs = func(i int, prev int, diff int, nums []int, out int) int {
// for j := i; j < len(nums); j++ {
// if nums[j]-prev == diff {
// k := [2]int{j, diff}
// if v, ok := dic[k]; ok {
// out += v
// } else {
// ret := dfs(j+1, nums[j], diff, nums, out+1)
// dic[k] = ret - out
// out = ret
// }
// }
// }
// return out
// }
// out := 0
// for i := 0; i < len(nums); i++ {
// for j := i + 1; j < len(nums); j++ {
// out = dfs(j+1, nums[j], nums[j]-nums[i], nums, out)
// }
// }
// return out
// }

/*

class C {
 int f(List<int> nums, int index, int curr, int prev, double dif) {
 int nr = 0;
 if (curr >= 3) {
 nr = 1; //if the current sequence has at least 3 elements, we count it
 }
 for (int i = index; i < nums.length; i++) {
 //check all posible numbers that could be included in the sequence
 double x = nums[i] - prev.toDouble();
 if (x == dif) {
 //"add" the number in the sequence
 nr = nr + f(nums, i + 1, curr + 1, nums[i], dif);
 }
 }
 return nr;
 }

 int numberOfArithmeticSlices(List<int> nums) {
 if (nums.length < 3) {
 return 0;
 }
 bool ok = true;
 int x = nums[0];
 for (int i = 1; i < nums.length; i++) {
 if (nums[i] != x) {
 ok = false;
 break;
 }
 }
 if (ok) {
 //if all numbers are equal
 //substract the combinations of n taken 1 and 2 from the total number of subsets
 //so we take all subsets with at least 3 elements
 int n = nums.length;
 int rez = (pow(2, n) - 1).toInt();
 rez = rez - n - n * (n - 1) ~/ 2;
 return rez;
 }
 int nr = 0;
 for (int i = 0; i < nums.length - 1; i++) {
 for (int j = i + 1; j < nums.length; j++) {
 //we take the first two elements of a subset
 //then the function searches for all subsets where the difference
 //between any 2 consecutive numbers is equal
 nr = nr + f(nums, j + 1, 2, nums[j], nums[j] - nums[i].toDouble());
 }
 }
 return nr;
 }
}


*/

funcfoo(nums []int, indexint, currentint, prevint, diffloat64) int {
varnRint=0
ifcurrent>=3 {
nR=1
 }
fori:=index; i<len(nums); i++ {
varxfloat64=float64(nums[i] -prev)
ifx==dif {
nR=nR+foo(nums, i+1, current+1, nums[i], dif)
 }
 }
returnnR
}
funcnumberOfArithmeticSlices(nums []int) int {
varnRint=0
iflen(nums) <3 {
return0
 }
varokbool=true
varxint=nums[0]
fori:=1; i<len(nums); i++ {
ifnums[i] !=x {
ok=false
break
 }
ifok {
varnint=len(nums)
varrezint=int(math.Pow(2, float64(n)) -1)
rez=rez-n-n*(n-1)/2
returnrez
 }
fori:=0; i<len(nums)-1; i++ {
forj:=i+1; j<len(nums); j++ {
nR=nR+foo(nums, j+1, 2, nums[j], float64(nums[j]-nums[i]))
 }
 }
 }
returnnR
}