首页 > 代码库 > LintCode-Subarray Sum Closest
LintCode-Subarray Sum Closest
Given an integer array, find a subarray with sum closest to zero. Return the indexes of the first number and last number.
Example
Given [-3, 1, 1, -3, 5], return [0, 2], [1, 3], [1, 1], [2, 2] or [0, 4]
Challenge
O(nlogn) time
Analysis:
s[i] = nums[0]+....nums[i], also record the index i into s[i]. Sort array s, and the minimum difference between two consecutive element, is the the subarray.
Solution:
1 class Element implements Comparable<Element>{ 2 int val; 3 int index; 4 public Element(int v, int i){ 5 val = v; 6 index = i; 7 } 8 9 public int compareTo(Element other){10 return this.val - other.val;11 }12 13 public int getIndex(){14 return index;15 }16 17 public int getValue(){18 return val;19 }20 }21 22 public class Solution {23 /**24 * @param nums: A list of integers25 * @return: A list of integers includes the index of the first number26 * and the index of the last number27 */28 public ArrayList<Integer> subarraySumClosest(int[] nums) {29 ArrayList<Integer> res = new ArrayList<Integer>();30 if (nums.length==0) return res;31 32 Element[] sums = new Element[nums.length+1];33 sums[0] = new Element(0,-1);34 int sum = 0;35 for (int i=0;i<nums.length;i++){36 sum += nums[i];37 sums[i+1] = new Element(sum,i);38 }39 40 Arrays.sort(sums);41 int min = Math.abs(sums[0].getValue() - sums[1].getValue());42 int start = Math.min(sums[0].getIndex(), sums[1].getIndex())+1;43 int end = Math.max(sums[0].getIndex(), sums[1].getIndex());44 for (int i=1;i<nums.length;i++){45 int diff = Math.abs(sums[i].getValue() - sums[i+1].getValue());46 if (diff<min){47 min = diff;48 start = Math.min(sums[i].getIndex(), sums[i+1].getIndex())+1;49 end = Math.max(sums[i].getIndex(), sums[i+1].getIndex());50 }51 }52 53 res.add(start);54 res.add(end);55 return res;56 }57 }
LintCode-Subarray Sum Closest
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。