0%

阿里编程题---数组四等分

阿里编程题—数组四等分

题目:
对于一个长度为N的整型数组A, 数组里所有的数都是正整数,对于两个满足0<=X <= Y <N的整数,
A[X], A[X+1] … A[Y]构成A的一个切片,记作(X, Y).
用三个下标 m1, m2, m3下标满足条件0 < m1, m1 + 1 < m2, m2 +1 < m3 < N – 1。
可以把这个整型数组分成(0, m1-1), (m1+1, m2-1), (m2+1, m3-1), (m3+1, N-1) 四个切片。
如果这四个切片的整数求和相等,称作“四等分”。 编写一个函数,求一个给定的整型数组是否可以四等分
要求: 函数的计算复杂度为O(N),使用的额外存储空间(除了输入的数组之外)最多为O(N)。

思路:因为要求数组是四等分,所以四个部分和是相等的,所以可以先从两端找k对m1,m3,同时记录sum值,然后对每一对m1,m3进行验证;如果m1,m3是符合条件的下标,那一定可以找到对应的m2将中间的数等分且和等于sum。

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
public class ArrayQuarter {
//找到所有能把数组头尾切分为两个相等部分的下标,并顺序存放在ArrayList中
public static boolean arrayQuarter(int[] arr){
//因为不确定有多少对m1,m3,所以用ArrayList将所有下标顺序存储,验证时一次取出三个就是m1,m3,sum
ArrayList<Integer> list = new ArrayList<>();
if (arr.length < 7)
return false;
int sum1 = arr[0];
int sum3 = arr[arr.length-1];
int m1 = 1;
int m3 = arr.length-2;
while(m1 < m3) {
if (sum1 > sum3) {
sum3 += arr[m3--];
}else if (sum1 < sum3) {
sum1 += arr[m1++];
} else {
list.add(m1);
list.add(m3);
list.add(sum1);
sum1 += arr[m1++];
sum3 += arr[m3--];
continue;
}
}
int[] result = checkingFind(arr, list);
if (result == null)
return false;
for (int i = 0; i < result.length; i++)
System.out.print(result[i] + " ");
System.out.println();
return true;
}

//对所有能将数组头尾切分为相等的下标进行验证,找到则返回m1,m2,m3数组
public static int[] checkingFind(int[] arr, ArrayList<Integer> list) {
if (list.size() == 0)
return null;
//依次检查所有m1,m3是否能找到匹配的m2满足题目要求
int i = 0;
int m1 = 0;
int m2 = 0;
int m3 = 0;
int sum = 0;
int[] result = {0, 0, 0};
while (i < list.size()-1) {
m1 = list.get(i++);
m3 = list.get(i++);
sum = list.get(i++);
m2 = findMiddleIndex(arr, m1, m3, sum);
if (m2 != 0){
result[0] = m1;
result[1] = m2;
result[2] = m3;
return result;
}
}
return null;
}

//根据m1,m3找m2,找到则返回m2下标,找不到则返回0
public static int findMiddleIndex(int[] arr, int m1, int m3, int sum) {
int p = m1 + 1;
int q = m3 - 1;
int sum2 = 0;
int sum3 = 0;
//从m1+1和m3-1往中间找m2
while (p < q) {
while (sum > sum2)
sum2 += arr[p++];
while (sum > sum3)
sum3 += arr[q--];

if (p == q && sum2 == sum3) {
return p;
}else {
return 0;
}
}
return 0;
}

public static void main(String[] args){
int[] A={2,5,1,5,8,4,1,7,3,1,7};
boolean result = arrayQuarter(A);
System.out.print(result);
}
}
-------------本文结束感谢您的阅读-------------