leetcode 927 Three Equal Parts

Leetcode 927. Three Equal Parts

– count how many one (if(num%3!=0) return[-1,-1])
– search from right side to left, until we found num/3 1s, this index is not final answer, but it define the pattern of 1s;
– from left, ignore 0s, and then match the pattern found in step 2, to get the first Endindex
– do another matching to found second EndIndex.

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
public int[] threeEqualParts(int[] A){
	int numOne = 0;
	for(int i: A){
		if(i==1) numOne++;
	}
	int[] noRes = { -1, -1 };
	if(numOne == 0) return new int[]{0, 2};
	if(numOne%3!=0) return noRes;
	int idxThird = 0;
	int temp = 0;
	for(int i = A.length-1; i >= 0; i--){
		if(A[i]==1){
			temp++;
			if(temp == numOne /3){
				idxThird = i;
				break;
			}
		}
	}
	int res1 = findEindIdx(A, 0, idxThird);
	if(res1 < 0) return noRes;
	int res2 = findEndIdx(A, res1+1, idxThird);
	if(res2<0) return noRes;
	return new int[]{res1, res2+1};
}

private int findEndIdx(int[] A, int left, int right){
		while(A[left]==0) left++;
		while(right < A.length){
			if(A[left] != A[right]) return -1;
			left++;
			right++;
		}
		return left-1;
}