思路
来自stack overflow:
The trick is to figure out a way to categorize the possible solutions and come up with a linear-time constant-space solution for each.
Consider the three ranges X = (0,2/3), Y = [2/3,1], Z = (1,2). At most one value can come from Z (if two values came from Z, then the sum would exceed 1+1=2). Similarly, at least one value must come from X. Suppose there were 3 values a <= b <= c so that 1 <= a+b+c <= 2 . Then, consider what possible classes of solutions are feasible:
A) `a \in X, b \in X, C \in X`
B) `a \in X, b \in X, C \in Y`
C) `a \in X, b \in X, C \in Z`
D) `a \in X, b \in Y, C \in Y`
E) `a \in X, b \in Y, C \in Z`
So how can we test each case?
Case A is incredibly easy to test: the sum is guaranteed to be below 2, so we just need to test the largest sum (largest 3 elements in X) exceeds 1.
Case C is incredibly easy to test: since the sum is guaranteed to be above 1, we only need to check if the sum is below 2. So in order to do that, we just need to test the smallest 2 values in X and the smallest value in Z
Cases D and E are similar to C (since the sum must be at least 4/3 > 1, choose the smallest possible values in each class).
Case B is the only tricky case. 0 < a+b < 4/3 and 2/3 <= c <= 1. To handle case B, we consider these intervals : X1 = (0, 1/2), X2 = [1/2 2/3), Y = [2/3, 1].
This results in following three valid cases :
B1. a in X1, b in X2, c in Y
B2. a in X1, b in X1, c in Y
B3. a in X2, b in X2, c in Y
Case B1 & B3 : Sum of three numbers is always greater than 1 so we take minimum values and check if it is smaller than 2 or not.
Case B2 : Sum of three numbers is always less than 2, so we take maximum sum and check if is greater than 1 or not.
So to summarize, the tests are:
- |X| >= 3 and Xmax(1) + Xmax(2) + Xmax(3) >= 1
- |X| >= 2, |Z| >= 1, and Xmin(1)+Xmin(2)+Zmin(1) <= 2
- |X| >= 1, |Y| >= 2, and Xmin(1)+Ymin(1)+Ymin(2) <= 2
- |X| >= 1, |Y| >= 1, |Z| >= 1, and Xmin(1)+Ymin(1)+Zmin(1) <= 2
- |X| >= 2, |Y| >= 1, and Xmax(1) + Xmax(2) + Ymin(1) < 2
- |X| >= 2, |Y| >= 1, and Xmin(1) + Xmin(2) + Ymax(1) > 1)
Each test can be performed in linear time and constant space (you only need to find Xmax(1), Xmax(2), Xmax(3), Xmin(1), Xmin(2), Ymin(1), Ymin(2), Ymax(1), Zmin(1), all of which can be found in one pass even if the data is not sorted)
Solution
Time: O(n)
Space: O(1)
public class Solution {
public int solve(ArrayList<String> A) {
// X = (0,2/3), Y = [2/3,1], Z = (1,2)
/*
|X| >= 3 and Xmax(1) + Xmax(2) + Xmax(3) >= 1
|X| >= 2, |Z| >= 1, and Xmin(1)+Xmin(2)+Zmin(1) <= 2
|X| >= 1, |Y| >= 2, and Xmin(1)+Ymin(1)+Ymin(2) <= 2
|X| >= 1, |Y| >= 1, |Z| >= 1, and Xmin(1)+Ymin(1)+Zmin(1) <= 2
|X| >= 2, |Y| >= 1, and Xmax(1) + Xmax(2) + Ymin(1) < 2
|X| >= 2, |Y| >= 1, and Xmin(1) + Xmin(2) + Ymax(1) > 1)
*/
Double Xmax1 = 0.0;
Double Xmax2 = 0.0;
Double Xmax3 = 0.0;
Double Xmin1 = 1.0;
Double Xmin2 = 1.0;
Double Ymin1 = 2.0;
Double Ymin2 = 2.0;
Double Ymax1 = 0.0;
Double Zmin1 = 2.0;
int X = 0, Y = 0, Z = 0;
for (int i = 0; i < A.size(); i ++) {
Double n = Double.valueOf(A.get(i));
if (n < ( 2.0 / 3.0)) {
X ++;
if (n > Xmax3 && n < Xmax2 && n < Xmax1) {
Xmax3 = n;
} else if (n > Xmax2 && n < Xmax1) {
Xmax3 = Xmax2;
Xmax2 = n;
} else if (n > Xmax1) {
Xmax3 = Xmax2;
Xmax2 = Xmax1;
Xmax1 = n;
}
if (n < Xmin2 && n > Xmin1) {
Xmin2 = n;
} else if (n < Xmin1) {
Xmin2 = Xmin1;
Xmin1 = n;
}
} else if (n <= 1) {
Y ++;
if (n > Ymax1) {
Ymax1 = n;
}
if (n < Ymin2 && n > Ymin1) {
Ymin2 = n;
} else if (n < Ymin1) {
Ymin2 = Ymin1;
Ymin1 = n;
}
} else if (n < 2) {
Z ++;
if (n < Zmin1) {
Zmin1 = n;
}
}
}
if (X >= 3) {
if (Xmax1 + Xmax2 + Xmax3 > 1) {
return 1;
}
}
if (X >= 2 && Z >= 1) {
if (Xmin1 + Xmin2 + Zmin1 < 2) {
return 1;
}
}
if (X >=1 && Y >= 2) {
if (Xmin1 + Ymin1 + Ymin2 < 2) {
return 1;
}
}
if (X >= 1 && Y >= 1 && Z >= 1) {
if (Xmin1 + Ymin1 + Zmin1 < 2) {
return 1;
}
}
if (X >=2 && Y >= 1) {
if (Xmax1 + Xmax2 + Ymin1 > 1 && Xmax1 + Xmax2 + Ymin1 < 2) {
return 1;
}
if (Xmin1 + Xmin2 + Ymax1 < 2 && Xmin1 + Xmin2 + Ymax1 > 1) {
return 1;
}
}
return 0;
}
}