最长的子阵列

Question

有人能为下面的问题提出一个简单的解决方案吗？

最长子数组：查找子数组中元素之和小于或等于“k”的最长连续子数组的长度。

输入为:< code>array和< code>k。

例子：

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

输出：

2个

解释:

子数组：｛1｝，｛2｝，｝3｝，1,2｝，2,3｝，{1,2,3}

{1，2} =

Answer 1

一种有效的方法是使用动态规划，以减少求和操作的数量。例如，如果您求和（1 2）=3，您不想再次求和（1 2 3）=6，您只希望求和（3 3）=6（其中前3已经计算并保存到哈希图中）。在这个解决方案中，哈希图表示从indexi到indexj的总和，格式为

    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 2

最简单、最朴素的答案是遍历数组，找到从当前索引开始的最长子数组。

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 3

O（n）方法。在高级别：

有2个指针开始和结束，开始是子数组的开始，结束是结束（独占）。用于保持子数组和的整型求和。一个 int len 来保持子数组 len。

将两者都设置为位置0。

>

继续移动end指针：

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

这将找到最长的子阵列与总和

移动start

sum -= arr[start];
start++;

返回到1，直到＜code＞end＜/code＞通过数组的最后一个元素

最后，您将找到最大长度（存储在len中）

将某些边缘情况的处理留给您（例如，如果数组中有一个元素具有值