寻找连续元素中和小于给定值的最大元素？

Question

所以，我有一个包含所有正自然数的数组。给定一个阈值，我需要找出连续的数字之和小于给定阈值的最大数字数量。

For example, 
IP: arr = {3,1,2,1}
Threshold = 5

O/P: 3

输入数组的最大长度可以是10^5。

基本上，我想到了一种算法，它计算原始数组子集中元素总和小于给定阈值的元素数量。但是，这将导致复杂度为O（N ^ 2）。有人能提供更好的算法吗？我不需要代码，只需要算法/伪代码即可。谢谢！

- John Lui

---

这回答了您的问题吗？数组中元素和小于等于k的最大元素数量。 - Kabir Kanha Arora

Answer 1

public static int maximumSum(int[] array, int t){
    int maxSum = 0;
    int curSum = 0;
    int start = 0;
    int end = 0;
    while(start < array.length){

        if(curSum > maxSum && curSum <= t){
            maxSum = curSum;
        }
        if(curSum <= t && end < array.length){
            curSum += array[end];
            end += 1;

        }
        else{
            curSum -= array[start];
            start+= 1;
        }
    }
    return maxSum;
}

这段代码的复杂度为O(2 * n)，实际上等同于O(n)。我无法想到任何改进方法。

- Abdulahi Abdinur

---

这个解决方案不正确。它找到的是元素之和最大的≤t的值，而不是最大值。 - Quang Vien

Answer 2

这可能有点粗糙，但应该能指向O(n)解决方案。

使用两个指针遍历列表，都从开头开始，我们称其中一个为lead（领导），另一个为trail（尾随），因为一个是领导，一个是尾随。

跟踪从trail到lead的总和；以及当前遇到的最长有效序列的长度。

当当前总和小于（或等于）阈值时，将lead指针向前移动，并通过添加它现在指向的值来调整总和。如果总和仍然小于（或等于）阈值，则从trail到lead的序列是可能的。

当当前总和大于阈值时，将trail指针向前移动。

继续直到lead指针到达末尾。

您需要填写详细信息并仔细实现它，但我认为它听起来很可靠。

- moreON

---

我按照您的建议进行了实现，并编辑了原始帖子以包含代码。但是，如果阈值非常大（8位数），并且数组中的元素数量为100000，则仍会出现超时。您能告诉我如何进一步优化我的代码吗？ - John Lui

不要重复计算总和。利用这样一个事实，即从Ai到Aj的总和等于从Ai到Aj-1的总和加上A[j]。 - moreON

Answer 3

我会尝试以下步骤：

• 从数组开头开始累加元素，直到达到阈值。将此子数组保存为临时结果。
• 然后从子数组开头移除一个元素，并尝试从另一侧添加新元素，直到再次达到阈值。如果结果更大，则用新结果替换以下结果。
• 继续直到数组结束。

- MaMazav

---

这听起来就像是我提出的解决方案，我们几乎同时发布了。这让我对他们更有信心。 - moreON

Answer 4

请尝试以下...

public int maximumElem(int[] array,int threshold)
{
   int sum = 0;
   for(int i=0;i<array.length;i++)
   {
     sum = sum + array[i]; //sum the values at each index
     if(sum >= threshold)  //check condition
       return (i+1); // if sum is reaching the threshold then return the index
   }
}

希望这能对你有所帮助...

如果你还有任何问题，请告诉我...

- Pavan Kumar K

---

但它不会返回最大计数。例如，如果输入数组是 6 1 2 3，并且 threshold = 5，你的代码将返回 1，而实际上应该返回 2。 - John Lui

对于6 1 2 3和阈值5，最大计数是6对吧？...那如果是7呢？ - Pavan Kumar K