给定一个整数数组，找到一个和最接近于零的子数组。返回第一个和最右一个指数。你的代码应该返回满足要求的子数组的起始位置和结束位置。
- 数据保证任意数的和都在[-2^31,2^31−1]范围内
在线评测地址：领扣题库官网
样例
输入:
[-3,1,1,-3,5]
输出:
[0,2]
解释: [0,2], [1,3], [1,1], [2,2], [0,4]算法：前缀和优化+排序贪心
- 先对数组求一遍前缀和，然后把前缀和排序，令排完序的前缀和是B数组
- 题目要求子数组的和最接近0，也就是B数组两个值相减最接近0
- 既然B数组两个值相减最接近0，也就是B数组两个最接近的数
- 对B数组排序，最接近的数肯定是相邻的
- 排完序后，我们只要找相邻元素做差就好了
B=sort(sums)for i in 1:n
res=B[i]-B[i-1]
ans=min(ans,res)
这样只需要一重枚举。
复杂度分析
N是输入的数组长度
时间复杂度
- 前缀和预处理O(N)
- 排序O(NlogN)
- 相邻元素做差O(N)
- 最终复杂度O(NlogN)
空间复杂度：开辟空间和输入数组同阶，O(N)
public class Solution {
static class Node implements Comparator<Node> {
public int value;
public int idx;
public Node() {
}
//value权值大小，arraysIdx在哪个数组里，idx在该数组的哪个位置> >
public Node(int value, int idx) {
this.value = value;
this.idx = idx;
}
public int compare(Node n1, Node n2) {
if(n1.value < n2.value) {
return 1;
} else {
return 0;
}
}
}
static Comparator<Node> cNode = new Comparator<Node>() {
public int compare(Node o1, Node o2) {
return o1.value - o2.value;
}
};
public int[] subarraySumClosest(int[] nums) {
// write your code here
//前缀和数组，并记录下标位置
ArrayList<Node> sums = new ArrayList<Node>();
for(int i = 0; i < nums.length; i++) {
if(i == 0) {
sums.add(new Node(nums[i], 0));
} else {
sums.add(new Node(nums[i] + sums.get(i - 1).value, i));
}
}
Collections.sort(sums, cNode);
//维护最小的绝对值以及位置
int mn = 2147483647;
int ans1 = 0, ans2 = 1;
for(int i = 0; i < sums.size(); i++) {
if(mn >= Math.abs(sums.get(i).value)) {
//[0,idx] 这段子数组的和
mn = Math.abs(sums.get(i).value);
ans1 = 0;
ans2 = sums.get(i).idx;
}
if(i > 0) {
// [lastidx+1,nowidx]这段子数组的和
int lastidx = sums.get(i - 1).idx;
int nowidx = sums.get(i).idx;
int lastsum = sums.get(i - 1).value;
int nowsum = sums.get(i).value;
if(mn >= Math.abs(nowsum - lastsum)) {
mn = Math.abs(nowsum - lastsum);
ans1 = Math.min(lastidx, nowidx) + 1;
ans2 = Math.max(lastidx, nowidx);
}
}
}
int []ans = new int[2];
ans[0] = ans1;
ans[1] = ans2;
return ans;
}
}更多题解参考：九章官网solution
