Question
Given an integer array, find a subarray with sum closest to zero. Return the indexes of the first number and last number.
Given [-3, 1, 1, -3, 5]
, return [0, 2]
, [1, 3]
,[1, 1]
, [2, 2]
or [0, 4]
.
Answer
这道题延续Subarray Sum的思路,即将[0, i]的sum存起来。这里构造了一个新的类,Pair。一方面存sum值,一方面存index。然后根据sum值排序,算相邻sum值的差值。差值最小的即为结果。时间复杂度是O(nlogn),空间复杂度是O(n)。
注意:假设[0-2]和[0-4]的sum值的差值最小,那么结果为index[3,4]
public class Solution { class Pair {
public int sum;
public int index;
public Pair(int sum, int index) {
this.sum = sum;
this.index = index;
}
}
/**
* @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[] result = new int[2];
if (nums == null || nums.length == 0) {
return result;
}
int len = nums.length;
int sum = 0;
List<Pair> list = new ArrayList<Pair>();
for (int i = 0; i < len; i++) {
sum += nums[i];
Pair tmp = new Pair(sum, i);
list.add(tmp);
}
Collections.sort(list, 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 < len; i++) {
int diff = list.get(i).sum - list.get(i - 1).sum;
if (diff < min) {
min = diff;
int index1 = list.get(i).index;
int index2 = list.get(i - 1).index;
if (index1 < index2) {
result[0] = index1 + 1;
result[1] = index2;
} else {
result[0] = index2 + 1;
result[1] = index1;
}
}
}
return result;
}
}