Как найти подмассив с ближайшей к нулю суммой или определенным значением t в O(nlogn)

Question

На самом деле это проблема № 10 главы 8 Programming Pearls 2nd edition. Он задал два вопроса: учитывая массив A[] целых чисел (положительных и неположительных), как найти непрерывный подмассив A[], сумма которого ближе всего к 0? Или ближе всего к определенному значению t?

Я могу придумать способ решить задачу, ближайшую к 0. Вычислить массив сумм префиксов S[], где S[i] = A[0]+A[1]+...+A[i]. А затем отсортируйте этот S по значению элемента вместе с сохраненной исходной информацией индекса, чтобы найти сумму подмассива, ближайшую к 0, просто итерируйте массив S и выполните diff двух соседних значений и обновите минимальный абсолютный diff.

Вопрос в том, как лучше всего решить вторую проблему? Ближайший к определенному значению т? Кто-нибудь может дать код или хотя бы алгоритм? (Если у кого-то есть лучшее решение проблемы, близкой к нулю, ответы также приветствуются)

Answer 1

Чтобы решить эту проблему, вы можете построить интервальное дерево по вашему собственному или сбалансированному бинарному поисковому дереву, или даже с помощью карты 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;
}

Answer 2

Вы можете адаптировать свой метод. Если у вас есть массив S префиксных сумм, как вы написали, и уже отсортированы в порядке возрастания значения суммы. Ключевой концепцией является не только проверка последовательных сумм префиксов, но и использование двух указателей для указания двух позиций в массиве. S, Написано в (слегка питоническом) псевдокоде:

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 проверяет, но если вы только подавляете такие случаи, я полагаю, что вы можете пропустить некоторые соответствующие случаи. Суть в том, что: примите эту идею, продумайте ее, но вам придется адаптировать ее для отрицательных чисел.

Примечание: я думаю, что это та же общая идея, которую Борис Странджев хотел выразить в своем решении. Тем не менее, я нашел это решение несколько трудным для чтения и трудным для понимания, поэтому я предлагаю свою формулировку этого.

Answer 3

Ваше решение для случая 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)
• самое главное, что вы не ищете end для каждого start с нуля - prefix[start] увеличивается в значении при переборе всех возможных значений для startЭто означает, что в каждой итерации вас интересуют только значения <= предыдущее значение end,
• Вы можете прекратить итерации, когда start > end
• вы берете лучшее из всех значений, полученных для всех start позиции.

Можно легко доказать, что это даст вам сложность O(n logn) для всего алгоритма.

Answer 4

Сложность времени решения: O(NlogN)
Пространство решения сложности: O(N)

[Обратите внимание, что эта проблема не может быть решена в O(N), как утверждают некоторые]

Алгоритм:-

1. Вычислить совокупный массив (здесь,cum[]) данного массива [Строка 10]
2. Сортировать накопительный массив [Строка 11]
3. Ответ минимален среди C[i]-C[i+1], $\forall$ 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
}

Answer 5

Я нашел этот вопрос случайно. Хотя это было какое-то время, я просто публикую это. O(nlogn) время, O(n) пространственный алгоритм. Это работает Java-код. Надеюсь, это поможет людям.

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);
    }
}

Answer 6

В качестве примечания: я согласен с алгоритмами, представленными здесь. Недавно у меня на голове появился другой алгоритм.

Сделайте еще одну копию A [], это B []. Внутри B [] каждый элемент имеет вид A[i]-t/n, что означает B[0]=A[0]-t/n, B[1]=A[1]-t/n ... B[п-1]=A[N-1]-t/ п. Затем вторая задача фактически преобразуется в первую, как только найден наименьший подрешетку из B [], ближайший к 0, в то же время найден подрешетку из [[], ближайший к t. (Это довольно сложно, если t не делится на n, тем не менее, точность должна быть выбрана подходящей. Также время выполнения O(n))

Answer 7

Не можем ли мы использовать динамическое программирование для решения этого вопроса, аналогичного алгоритму Кадане. Вот мое решение этой проблемы. Пожалуйста, прокомментируйте, если этот подход неверен.

#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;
}

Answer 8

Поразмыслив над этой проблемой, я обнаружил, что решение @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;
}

Answer 9

Я думаю, что есть небольшая ошибка относительно ближайшего к 0 решения. На последнем шаге мы должны не только проверить разницу между соседними элементами, но также и элементами, не находящимися рядом друг с другом, если один из них больше 0, а другой меньше 0.

• Извините, я думал, что должен получить ответы на все вопросы. Не видел, требуется только один.

Answer 10

Вот реализация кода 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;
    }
}