分割数组(将数组三等分)
//输入：一个自然数数组，选取其中2个数字num[i], num[j], 把数组三分，
// 每一部分的累加和（不包括分割点的数字）相等。
// 例：nums[] = [2,1,3,1,1,1,5,3]，选取nums[2] = 3, num[6] = 5,
// 三部分的和都是3. 则打印输出2, 6，
// 如果找不到符合条件的等分点，返回失败。（数组大小的量级最大是10^5）
public class DivideArray
{
/**
* 1、头指针从下标1开始，尾指针从倒数第二个元素开始
* 2、计算前后指针分割开的两块数组元素是否相等，小的一边向中间进位，直至相等。
* 3、然后计算中间区间的元素和是否与两边的元素和相等。
* 4、若中间元素和大于两边元素和，则继续移动指针；若小于则直接返回false
* @param inputArray
* @return
*/
public static boolean Div2Three(int[] inputArray)
{
if(inputArray == null || inputArray.length < 5)
{
return false;
}
int arrayLength = inputArray.length;
int startIndex = 1;
int endIndex = inputArray.length - 2;
int startSum = inputArray[0];
int endSum = inputArray[arrayLength-1];
int allSum = 0;
for (int i = 0; i < arrayLength; i++)
{
allSum += inputArray[i];
}
while (startIndex < endIndex - 1)
{
if(startSum == endSum) {
int midSum = allSum - 2 * startSum - inputArray[startIndex] - inputArray[endIndex];
if (midSum < endSum)
{
return false;
}
else if (midSum > endSum)
{
startIndex++;
endIndex--;
}
else
{
System.out.println("下标1：" + startIndex + " ,下标2：" + endIndex);
return true;
}
}
else if(endSum < startSum)
{
endSum += inputArray[endIndex];
endIndex--;
}
else
{
startSum += inputArray[startIndex];
startIndex++;
}
}
//若最终未找到对应的下标，则返回false
return false;
}
public static void main(String[] args)
{
int[] inputArray = {2, 1, 3, 1, 1, 1, 5, 3};
boolean isSuccess = Div2Three(inputArray);
if (isSuccess)
{
System.out.println("congratulations!");
return;
}
System.out.println("what a pity!");
}
}