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.
class Element implements Comparable<Element> {
int index;
int value;
public Element(int index, int value) {
this.index = index;
this.value = value;
}
public int compareTo(Element other) {
return this.value - other.value;
}
public int getIndex() {
return index;
}
public int getValue() {
return value;
}
}
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
int[] res = new int[2];
Element[] sums = new Element[nums.length+1];
sums[0] = new Element(-1, 0);
int sum = 0;
for (int i=0; i<nums.length; i++) {
sum += nums[i];
sums[i+1] = new Element(i, sum);
}
Arrays.sort(sums);
int minDif = Integer.MAX_VALUE;
for (int i=1; i<sums.length; i++) {
int dif = sums[i].getValue() - sums[i-1].getValue();
if (dif < minDif) {
minDif = dif;
res[0] = Math.min(sums[i].getIndex(), sums[i-1].getIndex()) + 1;
res[1] = Math.max(sums[i].getIndex(), sums[i-1].getIndex());
}
}
return res;
}
}