如何在O(nlogn)的时间复杂度内找到和最接近零或特定值t的子数组

12
实际上,这是《编程珠玑》第二版第8章的第10个问题。它提出了两个问题:给定一个整数数组A[](正数和非正数),如何找到一个连续的子数组,其和最接近0?或最接近某个值t?
我能想到一种解决最接近0问题的方法。计算前缀和数组S[],其中S[i] = A[0]+A[1]+...+A[i]。然后按照元素值对S进行排序,并保留其原始索引信息,以查找最接近0的子数组,只需迭代S数组并执行相邻两个值的差异,并更新最小绝对差。
问题是,解决第二个问题的最佳方法是什么?最接近某个值t?有人可以给出代码或至少算法吗?(如果有更好的解决方案来解决最接近零的问题,欢迎回答)

1
我有一个带有红色和黑色条目的已排序数组。如何找到最接近的红黑对?这如何解决您的问题? - David Eisenstat
在这个上下文中,“子数组”是指连续的数组元素,还是可以留下空白? - MvG
@MvG:我手头没有Bentley的副本,但我非常确定他的意思是连续的元素。 - Fred Foo
2
@DavidEisenstat 我不明白提示的意思... 排序后的数组不仅包含两个不同的值,那样怎么有帮助呢? - Henley
2
@DavidEisenstat 欢迎提供更详细的描述。 - Joey.Z
10个回答

7
为了解决这个问题,你可以自己构建区间树,或者平衡二叉搜索树,甚至可以从STL映射中获益,在O(nlogn)的时间复杂度内完成。
下面使用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;
}

1
这是我个人认为的正确解决方案。它需要更多的赞同票。基本上,它遍历整个数组,保持一个有序的前缀和历史记录,并为当前的“sum”在历史记录中找到最接近“sum-t”的最佳候选项。它是O(NlogN)并可以一次通过执行。 - OnurC
演示为我返回了c=0的随机数。 - BlueTrin
为什么我们不考虑最接近 (sum + c) 的候选者呢? - Konstantin Milyutin

4

您可以调整您的方法。假设您有一个数组S表示前缀和,就像您写的那样,并按照总和值的递增顺序进行排序。关键概念不仅是要检查相邻的前缀和,而是使用两个指针来指示数组S中的两个位置。以下是用(稍微Python化的)伪代码编写的内容:

left = 0                 # Initialize window of length 0 ...
right = 0                # ... at the beginning of the array
best = ∞                 # Keep track of best solution so far
while right < length(S): # Iterate until window reaches the end of the array
  diff = S[right] - S[left]
  if diff < t:           # Window is getting too small
    if t - diff < best:  # We have a new best subarray
      best = t - diff
      # remember left and right as well
    right = right + 1    # Make window bigger
  else:                  # Window getting too big
    if diff - t < best   # We have a new best subarray
      best = diff - t
      # remember left and right as well
    left = left + 1      # Make window smaller

复杂度受排序的限制。上述搜索将最多进行2n=O(n)次循环迭代,每次计算时间由常数限制。请注意,上述代码是为正整数t设计的。
该代码是为S中的正元素和正t设计的。如果出现任何负整数,您可能会遇到right的原始索引小于left的情况。因此,您将得到一个子序列总和为-t。您可以在if …<best检查中检查此条件,但如果只在那里压制这些情况,我相信您可能会错过一些相关情况。底线是:理解这个思路,仔细考虑,但您必须为负数做出适应。 注:认为这与Boris Strandjev想要在他的解决方案中表达的相同的一般思路。但是,我发现该解决方案有点难以阅读和理解,因此我提供了自己的表述。

1
我认为这是不正确的:首先,正如您所提到的,它不能处理负值。对于所有正值,您不需要预先计算和排序前缀和。可以使用您的算法解决正值子问题,修改为在leftright之间保持运行总和,并将其与t进行比较。 - OnurC
@OnurC:对于正数组元素来说,没有排序前缀和的方法也同样适用。我相信我的方法可能更容易扩展,以便它也能处理负值。但这更多是一种直觉感觉,我还没有想得很清楚。无论如何,虽然我的代码对于正数情况可能是不必要的,但我并不认为它是错误的。你呢?如果有的话,你能提供一个破解的例子吗? - MvG

2

我认为你对于0的情况的解决方案是可以的。这是我对于第二种情况的解决方案:

  • 你再次计算前缀和并排序。
  • 你将索引start初始化为0(排序后前缀数组中的第一个索引),将end初始化为last(前缀数组的最后一个索引)。
  • 你开始遍历start 0...last,并找到相应的end - 最后一个前缀和的索引,使得prefix[start] + prefix[end] > t。当你找到end时,start的最佳解决方案是prefix[start] + prefix[end]或者prefix[start] + prefix[end - 1](仅在end > 0时采用后者)。
  • 最重要的是,你不需要为每个start从头开始搜索end - 当迭代所有可能的start值时,prefix[start]的值会增加,这意味着在每次迭代中,你只关心小于end的先前值。
  • start > end时,你可以停止迭代。
  • 你取得所有start位置获得的最佳值。

可以很容易地证明,这将为整个算法提供O(n logn)的复杂度。


1
由于总体复杂度已经是 O(n*log(n)),你也可以使用二分查找来找到特定值的 startend。不过线性算法可能更容易编写 :) - Niklas B.
你能解释一下这部分吗:"当你发现结束时,最好的起始解决方案要么是prefix[start] + prefix[end],要么是prefix[start] + prefix[end - 1]" 假设排序后的前缀和为1、2、50、100、1000、10000、100000,而t为2。我们从prefix[0] + prefix[6]开始,即1 + 100000 = 100001。你告诉我最好的解决方案是这个,还是1 + 10000?实际上,最好的解决方案不是1 + 2吗? - Henley
好的,我理解了上面的内容,除了我不认为如果原始数组有负数时它实际上会起作用。我还认为你的解决方案在t != 0时会失败,因为你必须考虑原始数组中的两个前缀和结束的位置。因为如果t = 100,则200-100确实为100,但是100-200距离100很远。如果t = 0,则无所谓,因为+n和-n与0相等距离。 - Henley
以具体的例子来说,假设原始数组为:75、25、-75、-25、1。前缀和的前两个元素是100,所有元素的前缀和是1。假设t=100.1,并且你选择了1和100作为最佳前缀和对。1-100=-99,与其他候选项相差甚远。 - Henley
我的解决方案与你的类似,但有一些调整。因此,我会保留一个HashMap,将每个已排序的前缀和映射到它所代表的范围的索引。然后,在比较两个前缀和时,首先查看它们的索引。因此,您可以执行PrefixSum [i] - PrefixSum [j],其中i的前缀和覆盖比j更大的范围。 - Henley

1

我是意外发现了这个问题。虽然已经有一段时间了,但我还是想发布它。这是一个运行Java代码的O(nlogn)时间复杂度,O(n)空间复杂度的算法。希望这能帮助到大家。

import java.util.*;

public class FindSubarrayClosestToZero {

    void findSubarrayClosestToZero(int[] A) {
        int curSum = 0;
        List<Pair> list = new ArrayList<Pair>();

        // 1. create prefix array: curSum array
        for(int i = 0; i < A.length; i++) {
            curSum += A[i];
            Pair pair = new Pair(curSum, i);
            list.add(pair);
        }

        // 2. sort the prefix array by value
        Collections.sort(list, valueComparator);

        // printPairList(list);
        System.out.println();


        // 3. compute pair-wise value diff: Triple< diff, i, i+1>
        List<Triple> tList = new ArrayList<Triple>();
        for(int i=0; i < A.length-1; i++) {
            Pair p1 = list.get(i);
            Pair p2 = list.get(i+1);
            int valueDiff = p2.value - p1.value;

            Triple Triple = new Triple(valueDiff, p1.index, p2.index);          
            tList.add(Triple);
        }       

        // printTripleList(tList);
        System.out.println();

        // 4. Sort by min diff
        Collections.sort(tList, valueDiffComparator);
        // printTripleList(tList);

        Triple res = tList.get(0);

        int startIndex = Math.min(res.index1 + 1, res.index2);
        int endIndex = Math.max(res.index1 + 1, res.index2);

        System.out.println("\n\nThe subarray whose sum is closest to 0 is: ");
        for(int i= startIndex; i<=endIndex; i++) {
            System.out.print(" " + A[i]);
        }
    }

    class Pair {
        int value;
        int index;

        public Pair(int value, int index) {
            this.value = value;
            this.index = index;
        }
    }

    class Triple {
        int valueDiff;
        int index1;
        int index2;

        public Triple(int valueDiff, int index1, int index2) {
            this.valueDiff = valueDiff;
            this.index1 = index1;
            this.index2 = index2;
        }
    }

    public static Comparator<Pair> valueComparator = new Comparator<Pair>() {
        public int compare(Pair p1, Pair p2) {
            return p1.value - p2.value;
        }
    };      

    public static Comparator<Triple> valueDiffComparator = new Comparator<Triple>() {
        public int compare(Triple t1, Triple t2) {
            return t1.valueDiff - t2.valueDiff;
        }
    };

    void printPairList(List<Pair> list) {
        for(Pair pair : list) {
            System.out.println("<" + pair.value + " : " + pair.index + ">");
        }
    }

    void printTripleList(List<Triple> list) {
        for(Triple t : list) {
            System.out.println("<" + t.valueDiff + " : " + t.index1 + " , " + t.index2 + ">");
        }
    }


    public static void main(String[] args) {
        int A1[] = {8, -3, 2, 1, -4, 10, -5};       // -3, 2, 1
        int A2[] = {-3, 2, 4, -6, -8, 10, 11};      // 2, 4, 6
        int A3[] = {10, -2, -7};                                // 10, -2, -7

        FindSubarrayClosestToZero f = new FindSubarrayClosestToZero();
        f.findSubarrayClosestToZero(A1);
        f.findSubarrayClosestToZero(A2);
        f.findSubarrayClosestToZero(A3);
    }
}

1
解决方案时间复杂度:O(NlogN) 解决方案空间复杂度:O(N)
[请注意,有些人声称此问题可以在O(N)中解决]
算法: 1.计算给定数组的累积数组(这里是cum[])[第10行] 2.对累积数组进行排序[第11行] 3.答案是C [i] -C [i +1]的最小值,其中i∈[1,n-1](基于1的索引)[第12行]
C ++代码:
#include<bits/stdc++.h>
#define M 1000010
#define REP(i,n) for (int i=1;i<=n;i++) 
using namespace std;
typedef long long ll;
ll a[M],n,cum[M],ans=numeric_limits<ll>::max(); //cum->cumulative array
int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n; REP(i,n) cin>>a[i],cum[i]=cum[i-1]+a[i];
    sort(cum+1,cum+n+1);
    REP(i,n-1) ans=min(ans,cum[i+1]-cum[i]);
    cout<<ans; //min +ve difference from 0 we can get
}

0
经过更深入的思考,我发现 @frankyym 的方法是正确的。我对原始解决方案进行了一些改进,以下是我的代码:
#include <map>
#include <stdio.h>
#include <algorithm>
#include <limits.h>

using namespace std;

#define IDX_LOW_BOUND -2

// Return [i..j] range of A
pair<int, int> nearest_to_c(int A[], int n, int t) {
  map<int, int> bst;
  int presum, subsum, closest, i, j, start, end;
  bool unset;
  map<int, int>::iterator it;

  bst[0] = -1;
  // Barriers. Assume that no prefix sum is equal to INT_MAX or INT_MIN.
  bst[INT_MIN] = IDX_LOW_BOUND;
  bst[INT_MAX] = n;
  unset = true;
  // This initial value is always overwritten afterwards.
  closest = 0; 
  presum = 0;
  for (i = 0; i < n; ++i) {
    presum += A[i];
    for (it = bst.lower_bound(presum - t), j = 0; j < 2; --it, j++) {
      if (it->first == INT_MAX || it->first == INT_MIN) 
        continue;
      subsum = presum - it->first;
      if (unset || abs(closest - t) > abs(subsum - t)) {
        closest = subsum;
        start = it->second + 1;
        end = i;
        if (closest - t == 0)
          goto ret;
        unset = false;
      }
    }
    bst[presum] = i;
  }
ret:
  return make_pair(start, end);
}

int main() {
  int A[] = {10, 20, 30, 30, 20, 10, 10, 20};
  int t;
  scanf("%d", &t);
  pair<int, int> ans = nearest_to_c(A, 8, t);
  printf("[%d:%d]\n", ans.first, ans.second);
  return 0;
}

0

顺便提一下:我同意其他线程提供的算法。最近我脑海中还有另一个算法。

制作A[]的另一个副本B[]。在B[]内,每个元素都是A[i]-t/n,这意味着B[0]=A[0]-t/n,B[1]=A[1]-t/n ... B[n-1]=A[n-1]-t/n。然后第二个问题实际上转化为第一个问题,一旦找到最接近0的B[]子数组,同时找到最接近t的A[]子数组。(如果t不能被n整除,则有点棘手,但必须选择适当的精度。此外,运行时间为O(n))


0

我们能否使用动态规划来解决这个问题,类似于卡登算法。这是我对这个问题的解决方案,请评论是否有误。

#include <bits/stdc++.h>
using namespace std;
int main() {
 //code
 int test;
 cin>>test;
 while(test--){
     int n;
     cin>>n;
     vector<int> A(n);
     for(int i=0;i<n;i++)
         cin>>A[i];
    int closest_so_far=A[0];
    int closest_end_here=A[0];
    int start=0;
    int end=0;
    int lstart=0;
    int lend=0;
    for(int i=1;i<n;i++){
        if(abs(A[i]-0)<abs(A[i]+closest_end_here-0)){
             closest_end_here=A[i]-0;
             lstart=i;
             lend=i;
        }
        else{
             closest_end_here=A[i]+closest_end_here-0;
             lend=i;
        }
        if(abs(closest_end_here-0)<abs(closest_so_far-0)){
             closest_so_far=closest_end_here;
             start=lstart;
             end=lend;
        }
    }
    for(int i=start;i<=end;i++)
         cout<<A[i]<<" ";
         cout<<endl;
    cout<<closest_so_far<<endl;
    
 }
 return 0;
}


0

我觉得关于最接近0的解决方案有一个小bug。在最后一步,我们不仅应该检查相邻元素之间的差异,还应该检查不相邻的元素,如果其中一个大于0,另一个小于0。

  • 抱歉,我以为我应该得到这个问题的所有答案。没有看到只需要一个答案。

-1

这是一个Java代码实现:

public class Solution {
    /**
     * @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 ArrayList<Integer> subarraySumClosest(int[] nums) {
        // write your code here
        int len = nums.length;
        ArrayList<Integer> result = new ArrayList<Integer>();
        int[] sum = new int[len];
        HashMap<Integer,Integer> mapHelper = new HashMap<Integer,Integer>();
        int min = Integer.MAX_VALUE;
        int curr1 = 0;
        int curr2 = 0;
        sum[0] = nums[0];
        if(nums == null || len < 2){
            result.add(0);
            result.add(0);
            return result;
        }
        for(int i = 1;i < len;i++){
            sum[i] = sum[i-1] + nums[i];
        }
        for(int i = 0;i < len;i++){
            if(mapHelper.containsKey(sum[i])){
                result.add(mapHelper.get(sum[i])+1);
                result.add(i);
                return result;
            }
            else{
                mapHelper.put(sum[i],i);
            }
        }
        Arrays.sort(sum);
        for(int i = 0;i < len-1;i++){
            if(Math.abs(sum[i] - sum[i+1]) < min){
                min = Math.abs(sum[i] - sum[i+1]);
                curr1 = sum[i];
                curr2 = sum[i+1];
            }
        }
        if(mapHelper.get(curr1) < mapHelper.get(curr2)){
            result.add(mapHelper.get(curr1)+1);
            result.add(mapHelper.get(curr2));
        }
        else{
            result.add(mapHelper.get(curr2)+1);
            result.add(mapHelper.get(curr1)); 
        }
        return result;
    }
}

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接