三角形问题

/**
     * 有N根棍子,棍子i的长度为Ai,想从中取出3根棍子组成长度尽可能长的三角形
     * 输出最大周长,若无法组成,则返回0
     * sideLengthArray.length >= 3
     * @param sideLengthArray
     * @return
     */
    public int findMaxPerimeter(int[] sideLengthArray){
        /**
         * 思路:将给出棍子也就是数组按长度排序
         * 配合上组成三角形的条件，最长的一边小于另两边只和
         * 时间复杂度:排序使用归并排序 O(nlgn)
         * 在使用一次遍历找出结果
         * 综上 T(n) = O(nlgn)
         */
        int[] sortedArray = mergeSort(sideLengthArray, 0, sideLengthArray.length - 1);

        int maxPerimeter = 0;

        for (int i = 0; i < sortedArray.length; i++) {
            if(sortedArray[i] < sortedArray[i + 1] + sortedArray[i + 2]){
                //有解
                maxPerimeter = sortedArray[i] + sortedArray[i + 1] + sortedArray[i + 2];
                break;
            }
        }

        return maxPerimeter;
    }

    private int[] mergeSort(int[] sideLengthArray, int start, int end){
        if(sideLengthArray == null || sideLengthArray.length == 0){
            return sideLengthArray;
        }

        if(start == end){
            return new int[]{sideLengthArray[start]};
        }

        //归并排序注意middle的取法
        //(start+end)/2可能导致出现越界错误
        int middle = start + (end - start) / 2;
        int[] left = mergeSort(sideLengthArray, start, middle);
        int[] right = mergeSort(sideLengthArray, middle + 1, end);


        return merge(left, right);
    }

    private int[] merge(int[] left, int[] right){
        int size = left.length + right.length;
        int[] result = new int[size];
        int i = 0;
        int j = 0;
        int index = 0;
        while(i < left.length && j < right.length){
            if(left[i] > right[j]){
                result[index++] = left[i++];
            }else{
                result[index++] = right[j++];
            }
        }

        while(i < left.length){
            result[index++] = left[i++];
        }

        while(j < right.length){
            result[index++] = right[j++];
        }

        return result;
    }