如何在O(nlogn)中找到总和最接近零或某个值t的子数组

Question

实际上这是编程珍珠第2版第8章的问题#10.它提出了两个问题:给定一个整数数组A [](正数和非正数),你怎么能找到一个A []的连续子数组,其总和最接近0？或者最接近某个值t？

我可以想办法解决最接近0的问题.计算前缀和数组S [],其中S [i] = A [0] + A [1] + ... + A [i].然后根据元素值和保留的原始索引信息对此S进行排序,以找到最接近0的子阵列和,只需迭代S数组并执行两个相邻值的差异并更新最小绝对差值.

问题是,解决第二个问题的最佳方法是什么？最接近某个值t？任何人都可以提供代码或至少一个算法吗？(如果有人有最接近零问题的解决方案,也欢迎回答)

Answer 1

要解决此问题,您可以在O(nlogn)中通过自己的或平衡的二叉搜索树构建区间树,甚至可以从STL映射中获益.

以下是使用STL映射,使用lower_bound().

#include <map>
#include <iostream>
#include <algorithm>
using namespace std;

int A[] = {10,20,30,30,20,10,10,20};

// return (i, j) s.t. A[i] + ... + A[j] is nearest to value c
pair<int, int> nearest_to_c(int c, int n, int A[]) {
    map<int, int> bst;
    bst[0] = -1;
    // barriers
    bst[-int(1e9)] = -2;
    bst[int(1e9)] = n;

    int sum = 0, start, end, ret = c;
    for (int i=0; i<n; ++i) {
            sum += A[i];
            // it->first >= sum-c, and with the minimal value in bst
            map<int, int>::iterator it = bst.lower_bound(sum - c);
            int tmp = -(sum - c - it->first);
            if (tmp < ret) {
                    ret = tmp;
                    start = it->second + 1;
                    end = i;
            }

            --it;
            // it->first < sum-c, and with the maximal value in bst
            tmp = sum - c - it->first;
            if (tmp < ret) {
                    ret = tmp;
                    start = it->second + 1;
                    end = i;
            }

            bst[sum] = i;
    }
    return make_pair(start, end);
}

// demo
int main() {
    int c;
    cin >> c;
    pair<int, int> ans = nearest_to_c(c, 8, A);

    cout << ans.first << ' ' << ans.second << endl;
    return 0;
}

Answer 2

你对 0 案例的解决方案对我来说似乎没问题。这是我对第二种情况的解决方案：

• 您再次计算前缀和并排序。
• 您将索引初始化start为 0（已排序前缀数组中的第一个索引）end到last（前缀数组中的最后一个索引）
• 你开始迭代start0...last并且对于每个你找到相应的end- 最后一个索引，其中前缀和是这样的prefix[start]+ prefix[end]> t。当您发现 的end最佳解决方案start是prefix[start]+prefix[end]或prefix[start]+ prefix[end - 1]（仅当 > 0 时才采用后者end）
• 最重要的是，您不必从头开始搜索end每个值-迭代 的所有可能值时，值会增加，这意味着在每次迭代中，您只对 <= 的先前值感兴趣。startprefix[start]startend
• start您可以在>时停止迭代end
• 您可以从所有位置获得的所有值中选择最好的值start。

可以很容易地证明，这会给O(n logn)整个算法带来复杂性。