-
Notifications
You must be signed in to change notification settings - Fork 8
/
FairCandySwap.java
60 lines (49 loc) · 1.45 KB
/
FairCandySwap.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
package array;
// Source : https://leetcode.com/problems/fair-candy-swap/
// Id : 888
// Author : Fanlu Hai | https://github.com/Fanlu91/FanluLeetcode
// Date : 2019-06-10
// Topic : Array
// Level : Easy
// Other :
// Tips :
// Result : 100.00% 98.74%
public class FairCandySwap {
//25.90% 116 ms 93.87%
public int[] fairCandySwapOrigin(int[] A, int[] B) {
int diff = 0;
for (int a : A)
diff += a;
for (int b : B)
diff -= b;
diff /= 2;
for (int a : A) {
for (int b : B) {
if ((a - b) == diff)
return new int[]{a, b};
}
}
return null;
}
//learned from leetcode submission
// instead of using double for loops, using hash like function to store A / B array's result,
// then check using hash, reduce O(n2) to O(n)
// we can also use set+set.contains to do this which will be more adaptable but a bit slower in this case.
// 100.00% 98.74%
public int[] fairCandySwap(int[] A, int[] B) {
int diff = 0;
boolean[] hasA = new boolean[10001];
for (int a : A) {
diff += a;
hasA[a] = true;
}
for (int b : B)
diff -= b;
diff /= 2;
for (int b : B) {
if (b + diff > 0 && b + diff <= 100000 && hasA[b + diff])
return new int[]{b + diff, b};
}
return null;
}
}