Subarray Sum Closest

本文主要是介绍Subarray Sum Closest，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这道题让自己很囧，现在对于参考答案依然有嘻嘻哈哈的感觉。。。

参考点击打开链接

/**

     * @param nums: A list of integers
     * @return: A list of integers includes the index of the first number 
     *          and the index of the last number
     */
     
    class Pair{
        int sum;
        int index;
        public Pair(int sum, int index) {
            this.sum = sum;
            this.index = index;
        }
    } 
    
    public int[] subarraySumClosest(int[] nums) {
        if (nums == null || nums.length < 2) {
            return new int[]{0, 0};
        }
        Pair[] nPairs = new Pair[nums.length + 1];
        nPairs[0] = new Pair(0, 0);
        int presum = 0;
        for (int i = 1; i < nPairs.length; i++) {
            //nPairs[i] = new Pair(i, presum + nums[i - 1]);
            nPairs[i] = new Pair(presum + nums[i - 1], i);
            presum = nPairs[i].sum;
            
        }
        // int sum = 0;
        // for (int i = 1; i <= nums.length; i++) {
        //     sum = sum + nums[i - 1];
        //     nPairs[i] = new Pair(i, sum);
        // }
        int closest = Integer.MAX_VALUE;
        Arrays.sort(nPairs, new Comparator<Pair>() {
            public int compare(Pair m, Pair n){
                return m.sum - n.sum;
            }
        });
        int [] result = new int[2];
        for (int i = 1; i < nPairs.length; i++) {
            if (closest > (nPairs[i].sum - nPairs[i - 1].sum)) {
                closest = nPairs[i].sum - nPairs[i - 1].sum;
                int [] temp = new int[]{nPairs[i].index - 1, nPairs[i - 1].index - 1};
                Arrays.sort(temp);
                result[0] = temp[0] + 1;
                result[1] = temp[1];
            }
        }
        return result;
    }
     
    // 超时
    // public int[] subarraySumClosest(int[] nums) {
    //     // write your code here
    //     if (nums == null) {
    //         return new int[2];
    //     }
    //     int []arr = new int[2];
    //     if (nums.length < 2) {
    //         arr[0] = 0;
    //         arr[1] = 0;
    //         return arr;
    //     }
    //     int best = Integer.MAX_VALUE;
    //     int sum = 0;
    //     for (int i = 0; i < nums.length - 1; i++) {
    //         sum = nums[i];
    //         helper(arr, i, i, sum, best);
    //         for (int j = i + 1; j < nums.length; j++) {
    //             //1 sum = sum + sum[j];
    //             sum = sum + nums[j];
    //             //2 helper(arr, i, j, sum, best);犯了这样的错误，太可怕了, int 这种primitive类型的值改变都是局部的
    //             best = helper(arr, i, j, sum, best);
    //         }
    //     }
    //     return arr;
    // }
    
    // // 犯了这样的错误，太可怕了，int 这种primitive类型的值改变都是局部的
    // //private void helper(int []arr, int i, int j, int sum, int best) {
    // private int helper(int []arr, int i, int j, int sum, int best) {
    //     //int temp = Math.abs(sum - 0);看着就可笑
    //     int temp = Math.abs(sum);
    //     if (temp < best) {
    //         arr[0] = i;
    //         arr[1] = j;
    //         best = temp;
    //     }
    //     return best;
    // }

这篇关于Subarray Sum Closest的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---