记录阿里的在线面试题。

数组切片题

题设

对于一个长度为N的整型数组A,数组里所有的数都是正整数,对于两个满足0<=X<=Y<N的整数,A[X], A[X+1]...A[Y]构成A的一个切片,记作(X, Y)
用三个下标m1, m2, m3下标满足条件0<m1, m2+1<m2, m2+1<m3<N-1
可以把这个整型数组分成(0, m1-1), (m1+1, m2-1), (m2+1, m3-1), (m3+1, N-1)四个切片。如果这四个切片中的整数求和相等,称作“四等分”。
编写一个函数,求一个给定的整型数组是否可以四等分看,如果可以,返回一个布尔类型的true,如果不可以返回一个布尔类型的false

限制条件:数组A最多有1,000,000项,数组中的整数取值范围介于-1,000,000到1,000,000之间。
要求:函数的计算复杂度为O(N),使用额外存储空间(除了输入的数组之外)最多为O(N)
例子:
对于数组A=[1, 5, 1, 1, 1, 1, 4, 1, 7, 3, 7]存在下标2, 7, 9使得数组分成四个分片[2, 5], [1, 1, 1, 4], [7], [7],这三个分片内整数之和相等,所以对于这个数组,函数应该返回true
对于数组A=[10, 2, 11, 13, 1, 1, 1, 1, 1],找不到能把数组四等分的下标,所以函数应该返回false

解题过程

很遗憾,当时把题目看错了,因为室友前一天做了,所以以为下表元素是算在求和之内的。直到最后五分钟才意识到,已经晚了。

第一种思路当然是暴力求解,三个for循环,但是这显然是不行的。因为复杂度为O(N^3)

我这里采用的方法,受到了很多排序算法的启发,步骤如下:

  1. 使用三个游标,先初始化游标, 初始位置为1,3,5,计算四个子块的和。
  2. 然后进入while循环,判断子块和是否相等,如果相等返回true结束。
  3. 找出最小和的游标,然后将游标右移一位。
  4. 注意,游标移动的时候,可能会影响到后面的游标,因此要做出判断是否移动后续游标,更新其它游标位置和各子块的和。
  5. 重复2,3,4步骤,直到第四块和成为了最小块或三号游标到达了倒数第二个位置(底部),返回false结束。

我把这个方法叫做“暴力逻辑求解”,暂时没想到其他方法……

程序如下:

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
89
90
91
92
93
94
95
package cn.sjtunix.job;
import java.util.*;
public class sum3 {
/** 请完成下面这个函数,实现题目要求的功能 **/
/** 当然,你也可以不按照这个模板来作答,完全按照自己的想法来 ^-^ **/
static private int min(int[] a) {
int N = a.length;
int p = 0;
for(int i=0; i<N; i++) {
if(a[i] < a[p])
p = i;
}
return p;
}
static boolean resolve(int[] A) {
int N = A.length;
if(N < 7) return false;
// 准备三个游标
int p1 = 1;
int p2 = 3;
int p3 = 5;
// 存储区段和并初始化
int[] sum = new int[4];
sum[0] = A[0];
sum[1] = A[2];
sum[2] = A[4];
sum[3] = 0;
for(int i=6; i<N; i++)
sum[3] += A[i];
// 核心算法
while(p3<N-1) {
if(sum[0]==sum[1] && sum[1]==sum[2] && sum[2]==sum[3])
return true;
switch(min(sum)) {
case 0 :
sum[0] += A[p1];
sum[1] -= A[p1+1];
p1++;
if(p1+1==p2) {
sum[1] += A[p2];
sum[2] -= A[p2+1];
p2++;
}
if(p2+1==p3) {
sum[2] += A[p3];
sum[3] -= A[p3+1];
p3++;
}
break;
case 1 :
sum[1] += A[p2];
sum[2] -= A[p2+1];
p2++;
if(p2+1==p3) {
sum[2] += A[p3];
sum[3] -= A[p3+1];
p3++;
}
break;
case 2 :
sum[2] += A[p3];
sum[3] -= A[p3+1];
p3++;
break;
case 3 :
return false;
}
}
return false;
}
public static void main(String[] args){
ArrayList<Integer> inputs = new ArrayList<Integer>();
Scanner in = new Scanner(System.in);
String line = in.nextLine();
while(line != null && !line.isEmpty()) {
int value = Integer.parseInt(line.trim());
if(value == 0) break;
inputs.add(value);
line = in.nextLine();
}
int[] A = new int[inputs.size()];
for(int i=0; i<inputs.size(); i++) {
A[i] = inputs.get(i).intValue();
}
Boolean res = resolve(A);
System.out.println(String.valueOf(res));
}
}

程序复杂度满足O(N)要求。