前天在群里得知了一道阿里面试题，因为是别人口述，所以细节并不完整。
题目大意是这样的，有一个数组，去掉其中三个数，使数组剩下的四个部分和相等，且时间复杂度为O(n)。
想了很久如何使用一个循环来调度三个指针，因为在移动前两个指针的过程中，后一个指针亦必须作出反应，情况太多也太复杂。
今天想到一个方法，即在数组非负的情况下，采取从两头往中间挤压的方法可以定出前后两个区间，这时候中间部分就转变成了一个较好解决的问题----即去掉某一个数使数组剩下的两个部分相等。根据这种思路，可以写出下面的代码：
class test
{
public static void Partion(int[] nums){
int len = nums.length;
int i = 0;
int j = len-1;
int sum1 = nums[0];
int sum2 = nums[len-1];
while (i<j-1){
System.out.println(i+" "+j);
if (sum1 < sum2) { i++; sum1 = sum1 + nums[i];}
else if (sum1 > sum2) {j--; sum2 = sum2 + nums[j];}
else {
int p = i+2;
int q = j-2;
if (q-p < 2) { System.out.println("No solution!"); return;}
int sum3 = nums[p];
int sum4 = nums[q];
while (p != q){
System.out.println(p+" "+q);
if (sum3 < sum4) {p++; sum3 = sum3 + nums[p];}
else if (sum3 > sum4) {q--;sum4 = sum4 + nums[q];}
else {
//if (p == q) { System.out.println("three position are"+(i+1)+" "+(j-1)+" "+p); return;}
p++; sum3 = sum3 + nums[p];
}
}
if (sum3 == sum4 && sum3 - nums[p] == sum2) { System.out.println("three position are "+(i+1)+" "+(j-1)+" "+p); return;}
//System.out.println("No solution!"); return;
i++; sum1 = sum1 + nums[i];
}
}
System.out.println("No solution!");
}
public static void main(String[] args){
Partion(nums);
}
private static int[] nums = {4,33,1,3,56,2,2,5,1,1,1,1};
}
当然这个方法可以以O(n)的复杂度完成任务，但是总感觉是有漏洞的。。。