看到一道面试题：
给定一个int型的数组，找出两个位置，使得数组被分为三段，每段之和相等。
问存不存在这样的两个位置？
注意两个位置上的数字不属于任何一段，要求时间复杂度为O(n)。
用双循环的话，可以很容易的做到，但是时间复杂度是O(n2)，不满足要求。可以利用前缀和、后缀和的概念来解决。
用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
| package leetcode;
import java.util.HashMap;
public class PreSum {
public static void main(String[] args) {
int[] arr = {1, 4, 5, 2, 2, 2, 6, 5, 3, 7};
int sum = 0;
HashMap<Integer, Integer> suffixSumMap = new HashMap<>();
for (int i = arr.length - 1; i >= 0; i--) {
sum += arr[i];
suffixSumMap.put(sum, i);
}
int prefixSum = arr[0];
for (int i = 1; i < arr.length; i++) {
prefixSum += arr[i];
if (suffixSumMap.keySet().contains(prefixSum)) {
int m = i + 1;
int n = suffixSumMap.get(prefixSum) - 1;
if (prefixSum * 3 == sum - arr[m] - arr[n]) {
System.out.println("subSum: " + prefixSum);
System.out.println("bound1: " + m);
System.out.println("bound2: " + n);
break;
}
}
}
System.out.println("finish~~");
}
}
|
输出：
1
2
3
4
| subSum: 10
bound1: 3
bound2: 7
finish~~
|
