Lintcode: Subarray Sum Closest
sum lintcode Subarray Closest
2023-09-11 14:14:07 时间
Given an integer array, find a subarray with sum closest to zero. Return the indexes of the first number and last number. Have you met this question in a real interview? Yes 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+1] = nums[0]+....nums[i], also record the index i into s[i+1]. Sort array s, and the minimum difference between two consecutive element, is the the subarray.
1 class Element implements Comparable<Element> { 2 int index; 3 int value; 4 public Element(int index, int value) { 5 this.index = index; 6 this.value = value; 7 } 8 9 public int compareTo(Element other) { 10 return this.value - other.value; 11 } 12 13 public int getIndex() { 14 return index; 15 } 16 17 public int getValue() { 18 return value; 19 } 20 } 21 22 23 24 25 public class Solution { 26 /** 27 * @param nums: A list of integers 28 * @return: A list of integers includes the index of the first number 29 * and the index of the last number 30 */ 31 32 public int[] subarraySumClosest(int[] nums) { 33 // write your code here 34 int[] res = new int[2]; 35 Element[] sums = new Element[nums.length+1]; 36 sums[0] = new Element(-1, 0); 37 int sum = 0; 38 for (int i=0; i<nums.length; i++) { 39 sum += nums[i]; 40 sums[i+1] = new Element(i, sum); 41 } 42 Arrays.sort(sums); 43 int minDif = Integer.MAX_VALUE; 44 for (int i=1; i<sums.length; i++) { 45 int dif = sums[i].getValue() - sums[i-1].getValue(); 46 if (dif < minDif) { 47 minDif = dif; 48 res[0] = Math.min(sums[i].getIndex(), sums[i-1].getIndex()) + 1; 49 res[1] = Math.max(sums[i].getIndex(), sums[i-1].getIndex()); 50 } 51 } 52 return res; 53 } 54 }
相关文章
- (算法)Binary Tree Max Path Sum
- [Typescript] 126. Hard - Two Sum
- [LeetCode] Two Sum
- Scala集合的常用方法:sum/max/min/product
- 【C++竞赛 H】The sum problem
- 【LeetCode Weekly Contest 26 Q4】Split Array with Equal Sum
- [LeetCode]*124.Binary Tree Maximum Path Sum
- acdream 1431 Sum vs Product
- leetcode 437. Path Sum III
- C语言:定义一个计算两个整数的和的函数int sum(int a,int b),在主函数中输入两个整数x和y,调用sum(x,y)输出x+y的和。