最长子数组

Question

任何人都可以针对以下问题提出一个简单的解决方案。

Longest Sub-array: Find the length of longest contiguous sub-array where the sum of the elements in subarray is less than or equal to "k".

输入为：array 和 k。

示例：

Array = {1,2,3}, k = 3

输出：

2

解释：

Sub arrays : {1},{2},{3},{1,2},{2,3},{1,2,3}

{1,2} => max length = 2; 1+2 = 3 (<=k);

Answer 1

最简单和天真的答案是遍历数组并找到从当前索引开始的最长子数组。

int[] a = { 1,2,3,1,1,2,3,1,3 };
int k = 4;

int best_i = 0; // from index
int best_j = 0; // to index, so best length = j - i + 1
int best_sum = 0;

for (int i = 0; i < a.length; i++) { // starting index from beginning to end 
    int sum = 0;
    for (int j = i; j < a.length; j++) { // ending index from current to end
        sum += a[j];
        if (sum > k) break;
        if (j - i > best_j - best_i) { // best length found
            best_i = i;
            best_j = j;
            best_sum = sum;
        }
    }
}

System.out.println("best length = " + (best_j - best_i + 1) + " (indexes " + best_i + ".." + best_j + "), sum = " + best_sum);
// best length = 3 (indexes 3..5), sum = 4

Answer 2

一个有效的方法是使用动态规划来减少求和运算的次数。例如，如果您求和 (1 + 2) = 3，您不想再次求和 (1 + 2 + 3) = 6，您只想求和 (3 + 3) = 6（前 3 个已经计算并保存到哈希图中）。在此解决方案中，hashmap 表示从索引 i 到索引 j 的总和，格式为 <i, <j, sum>>。因此，您将所有从索引 i 开始的总和存储在内部哈希图中。请注意，您也可以使用二维数组而不是嵌套的 hashmap 结构，但是对于非常大的数据，您可能会在初始化该数组时遇到内存不足的异常。

    static int maxLength(int[] a, int k) {
        Map<Integer, Map<Integer, Long>> map = new HashMap<Integer, Map<Integer, Long>>();

        int maxLength = 0;
        for(int i = 0; i < a.length - 1; i++) {
            Map<Integer, Long> map2 = new HashMap<Integer, Long>();
            map2.put(i, (long)a[i]);
            map.put(i, map2);
            if(a[i] == k) {
                maxLength = 1;
            }
        }

        for(int l = 2; l <= a.length; l++) {
            long sum = 0;
            for(int i = 0; i <= a.length - l; i++) {
                int j = i + l - 1;
                Map<Integer, Long> map2 = map.get(i);
                sum = map2.get(j - 1) + a[j];
                map2.put(j, sum);

                if(sum <= k) {
                    if(l > maxLength) {
                        maxLength = l;
                    }
                }
            }
        }

        return maxLength;
    }

Answer 3

O(n) 方法。高级别：

有2个指针start和end，start是子数组的开始，end是结束（不包括）。一个 int sum 来保持子数组的总和。一个 int len 来保持子数组 len.

都设置到位置 0。

继续将 end 指针移动：

while (end < arr.length && sum + arr[end] <= k) {
    sum += arr[end];
    end ++;
}
if ((end - start) > len ) {
  len = (end-start);
}

哪个会找到最长的子数组 sum < k 以 start

移动start
```
sum -= arr[start];
start++;
```
回到1，直到end传递数组的最后一个元素

最后你会找到最大长度（存储在len）

将一些边缘情况的处理留给您（例如，如果数组中有一个元素的值为 > k。等等）

Answer 4

这里我只使用了for循环，但是我怀疑这个解决方案的复杂度，是O(n)还是O(n2)。看起来像一个 for 循环，但我不认为许多操作少于蛮力或两个 for 循环。

函数 maxLength(a, k) {

var maxLen = 0;
var currMaxLen = 0;
var currSum = 0;
var currIndex = 0;

for(index = 0; index < a.length; index++){
    currSum = currSum + a[index];

    if(currSum <= k){
        currMaxLen++;
    } else{
        //reset
        index = currIndex;
        currIndex++;
        maxLen = Math.max(maxLen, currMaxLen);
        currSum = 0;
        currMaxLen = 0;
    }
}
maxLen = Math.max(maxLen, currMaxLen);
return maxLen;

}

Answer 5

Python 实施

时间复杂度O(n)

不需要额外的 space

def longest_sub_array_sum(input_array: list, k: int) -> int:
    longest_size = 0
    
    if input_array:
        i = 0
        j = 1
        longest_size = 0 if input_array[i] != k else 1
        current_sum = input_array[i]
        
        while j < len(input_array):
            if current_sum <= k:
                if j - i > longest_size:
                    longest_size = j - i
                current_sum += input_array[j]
                j += 1

            elif current_sum > k:
                current_sum -= input_array[i]
                i += 1
                
    return longest_size

最长子数组

Longest Sub Array

java

arrays