Two elements whose sum is closest to zero
[Lintcode] Subarray Sum Closest
Given an integer array, find a subarray with sum closest to zero. Return the indexes of the first number and last number.
Example
Given [-3, 1, 1, -3, 5], return [0, 2], [1, 3], [1, 1], [2, 2] or [0, 4].
Challenge
O(nlogn) time
http://www.jiuzhang.com/solutions/subarray-sum-closest/
看到subarray又想到prefixSum。
我们算出所有的prefixSum，排个序。维护一个最小值closest，遍历一下排好序的sortedSum数组，相邻的两个看一下差如果小于closest，就更新答案。
O(nlogn) time: pre-sum with pre-sum value and index, sort presum;
s[i] = nums[0]+....nums[i], also record the index i into s[i]. Sort array s, and the minimum difference between two consecutive element, is the the subarray.
为避免对单个子串和是否为最小情形的单独考虑，我们可以采取类似链表 dummy 节点的方法规避，简化代码实现。故初始化sum_index时需要num_size + 1个。这里为避免 vector 反复扩充空间降低运行效率，使用resize一步到位。sum_index即最后结果中left_index和right_index等边界可以结合简单例子分析确定。
Using Treemap: to find close value
这个解法比较复杂，用到了treemap。 是通用与找closest to target k 的解法。简单解法参考subarray sum。排序即可。
https://codesolutiony.wordpress.com/2015/04/24/lintcode%EF%BC%9Asubarray-sum-closest-subarray-sum-closest-to-k/
https://shawnlincoding.wordpress.com/2015/08/31/481/
https://discuss.leetcode.com/topic/63618/how-to-find-the-subarray-that-has-sum-closest-to-zero-or-a-certain-value-t-in-o-nlogn
[Lintcode] Subarray Sum Closest
Given an integer array, find a subarray with sum closest to zero. Return the indexes of the first number and last number.
Example
Given [-3, 1, 1, -3, 5], return [0, 2], [1, 3], [1, 1], [2, 2] or [0, 4].
Challenge
O(nlogn) time
http://www.jiuzhang.com/solutions/subarray-sum-closest/
问：为什么需要一个 (0,0) 的初始 Pair?
答：
我们首先需要回顾一下，在 subarray 这节课里，我们讲过一个重要的知识点，叫做 Prefix Sum
比如对于数组 [1,2,3,4]，他的 Prefix Sum 是 [1,3,6,10]
分别表示 前1个数之和，前2个数之和，前3个数之和，前4个数之和
这个时候如果你想要知道 子数组 从下标 1 到下标 2 的这一段的和(2+3)，就用前 3个数之和 减去 前1个数之和 = PrefixSum[2] - PrefixSum[0] = 6 - 1 = 5
你可以看到这里的 前 x 个数，和具体对应的下标之间，存在 +-1 的问题
第 x 个数的下标是 x - 1，反之 下标 x 是第 x + 1 个数
那么问题来了，如果要计算 下标从 0~2 这一段呢？也就是第1个数到第3个数，因为那样会访问到 PrefixSum[-1]
所以我们把 PrefixSum 整体往后面移动一位，把第0位空出来表示前0个数之和，也就是0. => [0,1,3,6,10]
那么此时就用 PrefixSum[3] - PrefixSum[0] ，这样计算就更方便了。
此时，PrefixSum[i] 代表 前i个数之和，也就是 下标区间在 0 ~ i-1 这一段的和
那么回过头来看看，为什么我们需要一个 (0,0) 的 pair 呢？
因为 这个 0,0 代表的就是前0个数之和为0
一个 n 个数的数组， 变成了 prefix Sum 数组之后，会多一个数出来
看到subarray又想到prefixSum。
我们算出所有的prefixSum，排个序。维护一个最小值closest，遍历一下排好序的sortedSum数组，相邻的两个看一下差如果小于closest，就更新答案。
class Pair { int sum; int index; public Pair (int sum, int index) { this.sum = sum; this.index = index; } } public int[] subarraySumClosest(int[] nums) { int[] res = new int[2]; if (nums == null || nums.length == 0) {// return res; } if (nums.length == 1) {//\\ res[0] = 0; res[1] = 0; return res; } Pair[] prefixSum = new Pair[nums.length + 1]; prefixSum[0] = new Pair(0, 0);// for (int i = 1; i <= nums.length; i++) { prefixSum[i] = new Pair(prefixSum[i - 1].sum + nums[i - 1], i); } Pair[] sortedSum = prefixSum; Arrays.sort(sortedSum, new Comparator<Pair>() { //key here public int compare(Pair x, Pair y) { return x.sum - y.sum; } }); int closest = Integer.MAX_VALUE; for (int i = 1; i < sortedSum.length; i++) { if (sortedSum[i].sum - sortedSum[i - 1].sum < closest) { // may overflow closest = sortedSum[i].sum - sortedSum[i - 1].sum; res[0] = sortedSum[i].index - 1; res[1] = sortedSum[i - 1].index - 1; } } Arrays.sort(res); res[0]++; return res; }
public int[] subarraySumClosest(int[] nums) {
int[] res = new int[2];
if (nums == null || nums.length == 0) {
return res;
}
int len = nums.length;
if(len == 1) {
res[0] = res[1] = 0;
return res;
}
Pair[] sums = new Pair[len+1];
int prev = 0;
sums[0] = new Pair(0, 0);
for (int i = 1; i <= len; i++) {
sums[i] = new Pair(prev + nums[i-1], i);
prev = sums[i].sum;
}
Arrays.sort(sums, new Comparator<Pair>() {
public int compare(Pair a, Pair b) {
return a.sum - b.sum;
}
});
int ans = Integer.MAX_VALUE;
for (int i = 1; i <= len; i++) {
if (ans > sums[i].sum - sums[i-1].sum) {
ans = sums[i].sum - sums[i-1].sum;
int[] temp = new int[]{sums[i].index - 1, sums[i - 1].index - 1};
Arrays.sort(temp);
res[0] = temp[0] + 1;
res[1] = temp[1];
}
}
return res;
}
O(nlogn) time: pre-sum with pre-sum value and index, sort presum;
s[i] = nums[0]+....nums[i], also record the index i into s[i]. Sort array s, and the minimum difference between two consecutive element, is the the subarray.
28 public ArrayList<Integer> subarraySumClosest(int[] nums) { 29 ArrayList<Integer> res = new ArrayList<Integer>(); 30 if (nums.length==0) return res; 31 32 Element[] sums = new Element[nums.length+1]; 33 sums[0] = new Element(0,-1); 34 int sum = 0; 35 for (int i=0;i<nums.length;i++){ 36 sum += nums[i]; 37 sums[i+1] = new Element(sum,i); 38 } 39 40 Arrays.sort(sums); 41 int min = Math.abs(sums[0].getValue() - sums[1].getValue()); 42 int start = Math.min(sums[0].getIndex(), sums[1].getIndex())+1; 43 int end = Math.max(sums[0].getIndex(), sums[1].getIndex()); 44 for (int i=1;i<nums.length;i++){// if i start with 1, then should compare i with i-1; so we don't handle i=0 specially. 45 int diff = Math.abs(sums[i].getValue() - sums[i+1].getValue()); 46 if (diff<min){ 47 min = diff; 48 start = Math.min(sums[i].getIndex(), sums[i+1].getIndex())+1; 49 end = Math.max(sums[i].getIndex(), sums[i+1].getIndex()); 50 } 51 } 52 res.add(start); 54 res.add(end); 55 return res; 56 }http://algorithm.yuanbin.me/integer_array/subarray_sum_closest.html
为避免对单个子串和是否为最小情形的单独考虑，我们可以采取类似链表 dummy 节点的方法规避，简化代码实现。故初始化sum_index时需要num_size + 1个。这里为避免 vector 反复扩充空间降低运行效率，使用resize一步到位。sum_index即最后结果中left_index和right_index等边界可以结合简单例子分析确定。
vector<int> subarraySumClosest(vector<int> nums){
vector<int> result;
if (nums.empty()) {
return result;
}
const int num_size = nums.size();
vector<pair<int, int> > sum_index(num_size + 1);
for (int i = 0; i < num_size; ++i) {
sum_index[i + 1].first = sum_index[i].first + nums[i];
sum_index[i + 1].second = i + 1;
}
sort(sum_index.begin(), sum_index.end());
int min_diff = INT_MAX;
int closest_index = 1; // better, we compute start, end at last step.
for (int i = 1; i < num_size + 1; ++i) {
int sum_diff = abs(sum_index[i].first - sum_index[i - 1].first);
if (min_diff > sum_diff) {
min_diff = sum_diff;
closest_index = i;
}
}
int left_index = min(sum_index[closest_index - 1].second,\
sum_index[closest_index].second);
int right_index = -1 + max(sum_index[closest_index - 1].second,\
sum_index[closest_index].second);
result.push_back(left_index);
result.push_back(right_index);
return result;
}Using Treemap: to find close value
这个解法比较复杂，用到了treemap。 是通用与找closest to target k 的解法。简单解法参考subarray sum。排序即可。
https://codesolutiony.wordpress.com/2015/04/24/lintcode%EF%BC%9Asubarray-sum-closest-subarray-sum-closest-to-k/
public ArrayList<Integer> subarraySumClosest(int[] nums) { ArrayList<Integer> res = new ArrayList<Integer>(); if (nums == null || nums.length == 0) { return res; } TreeMap<Long, Integer> map = new TreeMap<Long, Integer>(); long sum = 0; long minDiff = (long)Integer.MAX_VALUE + 1; res.add(0); res.add(0); for (int i = 0; i < nums.length; i++) { sum += nums[i]; Entry floorEntry = map.floorEntry(sum); Entry ceilingEntry = map.ceilingEntry(sum); int curDiff = 0; if (floorEntry != null || ceilingEntry != null) { if (floorEntry == null || (ceilingEntry != null && Math.abs((long)floorEntry.getKey() - sum) > Math.abs((long)ceilingEntry.getKey() - sum))) { if (Math.abs((long)ceilingEntry.getKey() - sum) < minDiff) { res.set(0, (int)ceilingEntry.getValue() + 1); res.set(1, i); } } else { if (Math.abs((long)floorEntry.getKey() - sum) < minDiff) { res.set(0, (int)floorEntry.getValue() + 1); res.set(1, i); minDiff = Math.abs((long)floorEntry.getKey() - sum); } } } map.put(sum, i); } return res; }https://shawnlincoding.wordpress.com/2015/08/31/481/
public ArrayList<Integer> subarraySumClosest(int[] nums) { if (nums == null || nums.length == 0) { return null; } TreeMap<Integer, Integer> bst = new TreeMap<Integer, Integer>(); bst.put(0, -1); int prefix = 0; int minDiff = Integer.MAX_VALUE; ArrayList<Integer> res = new ArrayList<Integer>(); int left = 0, right = 0; for (int i = 0; i < nums.length; i++) { prefix += nums[i]; Map.Entry<Integer, Integer> pred = bst.floorEntry(prefix); if (pred != null) { int diff = Math.abs(pred.getKey() - prefix); if (minDiff > diff) { minDiff = diff; left = pred.getValue() + 1; right = i; } } Map.Entry<Integer, Integer> succ = bst.ceilingEntry(prefix); if (succ != null) { int diff = Math.abs(succ.getKey() - prefix); if (minDiff > diff) { minDiff = diff; left = succ.getValue() + 1; right = i; } } bst.put(prefix, i); } res.add(left); res.add(right); return res; }