-4

如何找到符合其总和大于给定值的子数组K？

我想出的是在序列的开始和结束处保持指针，并逐渐减去较小的指针以缩短序列。但似乎无效。为什么？

这是我的实现：

#include <iostream>

using namespace std;

int main() {
    while (!cin.eof()) {
        int caseCount;
        cin >> caseCount;
        int N, S;
        for (int i = 0; i < caseCount; i++) {
            cin >> N >> S;
            int * seq = new int[N];
            int maxSum = 0;
            for (int j = 0; j < N; j ++) {
                cin >> seq[j];
                maxSum += seq[j];
            }
            if (maxSum < S) {
                cout << 0 << endl;
                continue;
            }
            int left, right;
            left = 0;
            right = N-1;
            while(left < right) {
                if(seq[left] < seq[right]) {
                    if (maxSum - seq[left] < S) {
                        cout << right-left+1 << endl;
                        break;
                    } else {
                        maxSum -= seq[left];
                        left++;
                    }
                } else {
                    if (maxSum - seq[right] < S) {
                        cout << right-left+1 << endl;
                        break;
                    } else {
                        maxSum -= seq[right];
                        right--;
                    }
                }
            }
            if (left >= right) {
                cout << 1 << endl;
            }
        }
    }
    return 0;
}

样本输入：

2 // amount of sequences to input
10 15 // sequence 1 length and K
5 1 3 5 10 7 4 9 2 8 // sequence 1 data
5 11 // sequence 2 length and K
1 2 3 4 5 // sequence 2 data

样本输出：

2
3
4

4 回答 4

1

这是 Python 中的一个想法（因为它主要是一个算法问题），假设您的输入是自然数（感谢@ChrisOkasaki）。它在lists 上运行，但它应该很容易根据您的目的进行调整。两者start兼有end。它返回子数组的第一个和最后一个索引。

def find_minimal_length_subarr(arr, min_sum):
    found = False
    start = end = cur_start = cur_end = 0
    cur_sum = arr[cur_start]
    while cur_end < len(arr):
        if cur_start < cur_end:
            cur_sum += arr[cur_end]
        while cur_sum-arr[cur_start] >= min_sum:
            cur_sum -= arr[cur_start]
            cur_start += 1
        if cur_sum >= min_sum and (not found or cur_end-cur_start < end-start):
            start, end = cur_start, cur_end
            found = True
        cur_end += 1
    if found:
        return start, end

print find_minimal_length_subarr([11, 2, 3, 4, 9, 5, 6, 7, 8], 21) # (6, 8)

它从头开始并在min_sum未达到时向右扩展。当到达时，它会从左边缩短，而min_sum仍然到达。然后它又继续扩大。仅当找到更好（更短）的候选者时，才会替换较早的候选者。时间复杂度为 O(n)，空间复杂度为 O(1)。

于 2013-06-29T10:56:58.750 回答
1

这是基于 Thijs 算法的 C++ 中的工作示例，这似乎是解决您的问题的理想算法（如果我们理解正确的话。可以轻松更改它以找到第一个子序列或与谓词匹配的所有子序列）

#include <vector>
#include <utility>
#include <iostream>

using namespace std;
template<typename It>
pair<It, It> subseq_with_sum_greater(It begin, It end, typename It::value_type barrier)
{
    typename It::value_type current_sum = 0;
    pair<It, It> res = make_pair(begin, end);
    for(It current = begin; current < end; ++current)
    {
        current_sum += *current;
        while(current_sum > barrier and current_sum - *begin > barrier)
            current_sum -= *begin++;
        if(current_sum > barrier and distance(begin, current) < distance(res.first, res.second))
            res = make_pair(begin, current);
    }
    return res;
}

int main()
{
    vector<int> v = {5, 1, 3, 5, 10, 7, 4, 9, 2, 8};
    auto subseq = subseq_with_sum_greater(v.begin(), v.end(), 15);
    cout << distance(v.begin(), subseq.first) << ", " << distance(v.begin(), subseq.second);
}

输出是4, 5，子序列的索引。请注意，std::distance仅对 RandomAccess 迭代器（如 std::vector 上的迭代器）使用 O(1) 复杂度，size_t current_distance, minimal_distance如果您想在其他容器上使用这种模板，您可能需要添加变量。此外，当没有找到任何子序列时，该算法会返回一begin, end对，这使得很难知道这是答案还是没有子序列匹配。根据您的情况，您可能希望获得更精确的输出。

于 2013-06-29T11:53:21.750 回答
0

你的算法不正确。你基本上只检查序列的中间，这没有任何意义。相反，您应该从数组开头的两个索引开始，只要子范围的总和小于 K，就向右递增。当它变大时，开始向左递增，直到它再次变小。现在您有了最短子序列的候选 - 保存它。重复直到正确不会超过数组的末尾，如果新的候选人更短，则更新您的候选人。

于 2013-06-29T10:56:30.010 回答
0

这也适用于负面内容：

def s(arr, K):
   candidate = None
   for l,r in [(x,x+1) for x in range(len(arr))]:
     while sum(arr[l:r]) < K and r <= len(arr): r = r + 1
     if K <= sum(arr[l:r]):
       if candidate is None or r-l < candidate[1]-candidate[0]:
         candidate = (l,r)
   return candidate # ending index will be exclusive

在 C++ 中：

typedef struct {
    bool found; int l; int r; 
} range;

int sum(int arr[], int arr_n, int l, int r) {
    int sum = 0;
    for (int i=l; i<r && i<arr_n; i++)
        sum+=arr[i];
    return sum;
}

range s(int arr[], int K, int arr_n) {
    bool found = false; int c_l; int c_r;
    for (int l=0; l<arr_n; l++) {
        int r = l+1;
        while (sum(arr, arr_n, l, r) < K && r <= arr_n) r++;
        if (K <= sum(arr, arr_n, l, r))
            if (!found || r-l < c_r-c_l) {
                c_l = l; c_r = r; found = true;
            }
    }
    return (range){found, c_l, c_r};
}
于 2013-06-29T22:27:51.087 回答