将数组分为4个子数组,且它们的和相等
这是一道某名企的开发实习岗的在线笔试题,题目描述是这样的:
输入为一个int类型的数组,在数组中选择三个切割点,将该数组分为四个子数组(不包含切割点),若这四个子数组的和相等,则返回true, 否则返回false.
例如:
Input : [3, 2, 4, 1, 4, 9, 5, 10, 1, 2, 2]
Output : true. (三个切割点下标为2, 5, 7. 四个子数组为[3,2], [1,4], [5], [1,2,2])
Input : [1, 2, 4, 2, 4, 5, 6, 1, 2, 3]
Output : false.
要求时间复杂度为O(n), 空间复杂度为O(n).
解题思路:
时间复杂度为O(n), 所以不能采用暴力求解。先设两个指针i, j,i 指向数组头,j指向数组尾部,维护leftSum = sum[0]+..sum[i], rightSum = sum[j] + ... sum[a.length-1]。若leftSum < rightSum , 则 i++, 更新leftSum; 若leftSum > rightSum, 则j--, 更新rightSum. 一直重复此步骤,直到leftSum = rightSum或i>=j停止,若i>=j,则返回false, 若leftSum = rightSum, 说明暂时找到了第一和第三个切割点,现在要在i, j之间找第二个切割点,这时我们可以利用HashMap在O(1)的时间复杂度内判断能否找到第二个合法的切割点。方法如下:HashMap里放的键值对为(sum[i],i). 其中sum[i]代表数组a从第0个位置到第i个位置的元素之和。这样我们可以在leftSum = rigthSum的基础下, 用map.get(leftSum + a[first_index] + leftSum)来返回第二个切割点的下标,若不存在或者返回的下标seconde_index >= third_index, 则寻找失败,继续下一次探测,否则找到第二个切割点,返回true.
Java代码如下:
public static boolean ifExistFourEquals(int[] arr){
int len = arr.length;
if(len < 7) {
System.out.println("can not split it into four equals!");
return false;
}
int[] sum = new int[len];
Map<Integer,Integer> map = new HashMap();
sum[0]=arr[0];
map.put(sum[0],0);
for(int i =1;i<len;i++){
sum[i]=sum[i-1]+arr[i];
map.put(sum[i],i);
}
int first_index = 0;
int third_index = len-1;
int leftSum = arr[0];
int rightSum = arr[len-1];
while(true) {
while (leftSum != rightSum && first_index < third_index) {
while (leftSum < rightSum) {
++first_index;
leftSum += arr[first_index];
}
while (leftSum > rightSum) {
--third_index;
rightSum += arr[third_index];
}
}
if(first_index >= third_index) {
System.out.println("can not split it into four equals!");
return false;
}
//leftSum == rightSum
else {
++first_index;
--third_index;
if(!map.containsKey(leftSum+arr[first_index]+leftSum)){
leftSum += arr[first_index];
rightSum += arr[third_index];
continue;
}
else{
int second_index = map.get(leftSum + arr[first_index] + leftSum);
//失败,继续下一次探测
if(second_index >= third_index){
leftSum += arr[first_index];
rightSum += arr[third_index];
continue;
}
else{
if(sum[second_index] - sum[first_index] == leftSum &&
sum[third_index-1] - sum[second_index+1] == rightSum){
++second_index;
System.out.println("Index 1:" + first_index +";\nIndex 2:" + second_index +";\nIndex 3:"+third_index);
return true;
}
}
}
}
}
}