給定一個整數數組，找到一個和最接近於零的子數組。返回第一個和最右一個指數。你的代碼應該返回滿足要求的子數組的起始位置和結束位置。
- 數據保證任意數的和都在[-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