当前位置：首页 > news >正文

【算法】【数组与矩阵模块】正数组中累加和为给定值的最长子数组长度，空间复杂度O(1)解法

news 2025/8/22 19:30:36

前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
给定正数组，求正数组中累加和为给定值的最长子数组长度
如：
arr = {1, 3, 2, 5, 4, 7, 8}， k = 10
结果为：3，数组{3，2，5} 为最长子数组

解决方案

原问题：
解法一（空间O(n)）:
参考：

https://swzhao.blog.csdn.net/article/details/126942975

该解法可以适配非正数无序数组，但是空间复杂度为O(n)
解法二（空间O(1)）：
1、申请两个变量left，right，作为滑动窗口的两端，申请一个变量sum作为滑动窗口的和，实时计算
2、在left和right滑动的过程中，sum作为和，如果 sum < k ，说明和小了，right++扩大窗口
3、反之说明和大了，left++减小窗口即可，因为正数数组，因此和sum一定会减少

代码编写

java语言版本

原问题：

    public static int maxLen2K(int[] arr, int k) {if (arr == null || arr.length == 0) {return 0;}// 两个游标从开始游走left<= rightint left = 0, right = 0;// sum为了实时保存left到right的和int sum = arr[0];// 结果int len = 0;while (left <= right && right <= arr.length) {if (sum == k) {len = Math.max(len, right - left + 1);// 这里right尽可能的远right++;// 更新sumsum += right > arr.length ? 0 : arr[right];}else if (sum < k) {// 小了，需要拓展right++;sum += right >= arr.length ? 0 : arr[right];}else {// 大了，需要缩小sum -= arr[left];left++;}}return len;}public static void main(String[] args) {int[] ints = {1, 3, 2, 5, 4, 7, 8};int[] ints1 = {-3, -1, -4, 6, 3, -3, 5, 6, 0};int[] ints2 = {0, 1, 1, 0, 0, 0, 0, 1, 0};int[] ints3 = {3, -2, -4, 0, 6};//System.out.println(myGetMaxLenth(ints, 8));//System.out.println(myGetMaxLengthFromPG(ints1));//System.out.println(myGetMaxLengthFrom01(ints2));System.out.println(maxLen2K(ints, 10));}