Subarray Sum Closest

Problem:
Given an integer array, find a subarray with sum closest to zero. Return the indexes of the first number and last number.

2/23/2018 update
Again well explained below.
Solution with better format:
public class Solution {
    /*
     * @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 index;
        int sum;
        public Pair(int index, int sum) {
            this.index = index;
            this.sum = sum;
            }
    }
    public int[] subarraySumClosest(int[] nums) {
        // write your code here
        if (nums == null || nums.length == 0) 
            return new int[]{};
        Pair[] pairs = new Pair[nums.length + 1];
        pairs[0] = new Pair(-1, 0);
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            pairs[i + 1] = new Pair(i, sum);
        }

        Arrays.sort(pairs, new Comparator<Pair>(){
            public int compare(Pair a, Pair b) {
                return a.sum - b.sum;
            }
        });

        int[] res =  new int[2];
        int minSum = Integer.MAX_VALUE;
        for (int i = 1; i < pairs.length; i++) {
            if ((pairs[i].sum - pairs[i - 1].sum) < minSum) {
                minSum = pairs[i].sum - pairs[i - 1].sum;
                int[] temp = new int[] {pairs[i].index, pairs[i - 1].index};
                Arrays.sort(temp);
                res[0] = temp[0] + 1;
                res[1] = temp[1];
            }
        }
        return res;
    }
}


-------------------------------------------------------------------------------------------
思路:
比如这个例子[-3,1,1,-3,5], prefixsum数组为[0, -3, -2, -1, -4, 1]. 求subarry sum离0最近,也就是求prefixsum之间的差最接近0。求一个数组中任意2个数最相近的方法就是排序,然后检查相邻的2个数的差。

实现:
在找到临时的答案时temp数组的index应该是prefixsum index-1:int[] temp = new int[] {pairs[i].index-1, pairs[i-1].index-1};
代码如下:



 class Pair {  
   int index;  
   int sum;  
   public Pair(int index, int sum) {  
     this.index = index;  
     this.sum = sum;  
   }  
 }  
 public class Solution {  
   /*  
    * @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  
    */  
   public int[] subarraySumClosest(int[] nums) {  
     // write your code here  
     if( nums.length == 0 || nums == null)   
       return null;  
     int[] res = new int[2];  
     // get all prefixsums  
     int prev = 0;  
     Pair[] pairs = new Pair[nums.length+1];  
     pairs[0] = new Pair(0,0);  
     for(int i = 1; i <= nums.length; i++) {  
       int sum = prev + nums[i-1];  
       pairs[i] = new Pair(i, sum);  
       prev = sum;  
     }  
     // sort prefixsums  
     Arrays.sort(pairs, new Comparator<Pair>(){  
       public int compare(Pair a, Pair b) {  
         return a.sum - b.sum;  
       }   
     });  
     int min = Integer.MAX_VALUE;  
     for(int i = 1; i <= nums.length; i++)  
     {  
       if( pairs[i].sum - pairs[i-1].sum < min ) {  
         min = pairs[i].sum - pairs[i-1].sum;  
         int[] temp = new int[] {pairs[i].index-1, pairs[i-1].index-1};  
         Arrays.sort(temp);  
         res[0] = temp[0] + 1;  
         res[1] = temp[1];  
       }  
     }  
     return res;  
   }  
 }  

评论

此博客中的热门博文

776. Split BST

663. Equal Tree Partition

532. K-diff Pairs in an Array