-
Notifications
You must be signed in to change notification settings - Fork 1
/
css.go
59 lines (56 loc) · 1.06 KB
/
css.go
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
package css
func checkSubArraySum(nums []int, k int) bool {
return bruteForce(nums, k)
}
// bruteForce time complexity O(n^2) space complexity O(1)
func bruteForce(nums []int, k int) bool {
n := len(nums)
if n < 2 {
return false
}
var sum int
for i := range nums {
sum = 0
for j := i; j < n; j++ {
sum += nums[j]
if sum == k || (k != 0 && sum%k == 0) {
if j > i {
// at least 2 that sum up to k
return true
}
}
}
}
return false
}
// preSumHash time complexity o(N), space complexity O(N)
func preSumHash(nums []int, k int) bool {
n := len(nums)
if n < 2 {
return false
}
// key is the sum%k, value is index
// based on this math equation
// sum1 % k = x ----- eq1
// sum2 % k = x ----- eq2
// then (sum1-sum2) % k = x - x = 0 ------ eq3
hash := make(map[int]int, n)
// edge case
hash[0] = -1
var sum int
for i := range nums {
sum += nums[i]
if k != 0 {
sum %= k
}
if v, exists := hash[sum]; exists {
// found one based on eq3
if i-v > 1 {
return true
}
} else {
hash[sum] = i
}
}
return false
}