简记平衡点问题的实现及改进

  从论坛上看到一个平衡点的考题，问题如下：

引用

1.平衡点问题
  平衡点：比如int[] numbers = {1,3,5,7,8,25,4,20}; 25前面的总和为24，25后面的总和也是24，25这个点就是平衡点；假如一个数组中的元素，其前面的部分等于后面的部分，那么这个点的位序就是平衡点
要求：返回任何一个平衡点

原帖地址：http://www.iteye.com/topic/600079


    跟帖中有人采用了求和，然后从头遍历的方法，马背想换种思路，采用从头尾向中间步进的方法，简单实现了一下，第一版的代码如下：

package org.eric;

/**
 * 测试找出平衡点。
 * 平衡点：数组中某一个元素，其前面元素的总和和后面的元素总和相等，则此元素为平衡点。
 * @author 马背{eric.liu}  http://mabei.iteye.com
 */
public class BalanceElement {

    public static void main(String[] argc) {
        //测试数据：{1, 3, 5, 7, 8, 25, 4, 20}
        int[] elements = new int[]{1, 3, 5, 7, 8, 25, 4, 20};
        findSomeOneBalance(elements);
    }
   
    public static void findSomeOneBalance(int[] elements) {
        //判断不合理情况
        if (elements == null || elements.length < 3) {
            System.out.println("==bad elements ==");
            return;
        }

        int pos = 0;          //最终找到的平衡点的位置
        int element = 0;      //平衡点的值

        int n = elements.length;        //当前判断剩余的元素，初始值为元素总长度
        int headPos = -1;               //循环判断中头部元素位置
        int tailPos = elements.length;  //循环判断中尾部元素位置
        int head = 0;                   //头部值的累加和
        int tail = 0;                   //尾部值的累加和
        boolean headStep = true;        //头部累加在循环判断中下一步是否前进
        boolean tailStep = true;        //尾部累加在循环判断中下一步是否前进

        //循环判断
        do {
            if (headStep) {
                head += elements[++headPos];
                n--;
            }
            if (tailStep) {
                tail += elements[--tailPos];
                n--;
            }

            if (head < tail) {
                headStep = true;
                tailStep = false;
            } else if (head > tail) {
                headStep = false;
                tailStep = true;
            } else {
                pos = headPos + 1;
                element = elements[pos];
            }

        } while (n > 1);

        //输出结果
        if (pos != 0) {
            System.out.println("==find balance element pos is:" + pos
                    + ",and value is:" + element);
        } else {
            System.out.println("==can't find balance element ==");
        }
    }
}

    此实现马上就发现有重要的bug，当head和tail相等的时候，中间可能还有不止一个元素，即只是相等不能作为判断平衡点的唯一标准，修改之后，第二版程序如下：

   

            if (head < tail) {
                headStep = true;
                tailStep = false;
            } else if (head > tail) {
                headStep = false;
                tailStep = true;
            } else if(n==1) {          //注意此处n==1的判断
                pos = headPos + 1;
                element = elements[pos];
            }

    

    考虑到一些特殊情况，例如：数组中可能存在多个平衡点、两个平衡点相邻等，进一步修改到第三版：


     

           if (head < tail) {
                headStep = true;
                tailStep = false;
            } else if (head > tail) {
                headStep = false;
                tailStep = true;
            } else if (n == 1 || n == 0) {      //n=0时代表两个平衡点相邻
                pos = headPos + n;              //+n取代固定+1，平衡点相邻的时候，总是取靠近head的
                element = elements[pos];
            }  

      

      最后针对上面这个版本，马背测试了一些模拟数据，暂时没有发现问题：

      

• {1,1,1,1,2,1}
• {1, 1, 0, 0, 1, 1}
• {1,2,0,2,1}

附最后第三版源代码：