网络科技官网网站建设,用来做问卷调查的网站,深圳专业做网站排名公司,dw做网站有雪花效果目录前言问题介绍解决方案代码编写java语言版本c语言版本c语言版本思考感悟写在最后前言
当前所有算法都使用测试用例运行过#xff0c;但是不保证100%的测试用例#xff0c;如果存在问题务必联系批评指正~ 在此感谢左大神让我对算法有了新的感悟认识#xff01; 问题介绍 …
目录前言问题介绍解决方案代码编写java语言版本c语言版本c语言版本思考感悟写在最后前言
当前所有算法都使用测试用例运行过但是不保证100%的测试用例如果存在问题务必联系批评指正~ 在此感谢左大神让我对算法有了新的感悟认识 问题介绍
原问题 给定正数组求正数组中累加和为给定值的最长子数组长度 如 arr {1, 3, 2, 5, 4, 7, 8} k 10 结果为3数组{325} 为最长子数组
解决方案
原问题 解法一空间O(n): 参考 https://swzhao.blog.csdn.net/article/details/126942975 该解法可以适配非正数无序数组但是空间复杂度为O(n) 解法二空间O(1) 1、申请两个变量leftright作为滑动窗口的两端申请一个变量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));}c语言版本
正在学习中
c语言版本
正在学习中
思考感悟
其实参考里面的解法我认为是这种类型问题的统一解法这篇文章主要介绍的是滑动窗口的玩法有兴趣可以看一下还是比较简单的。
写在最后 方案和代码仅提供学习和思考使用切勿随意滥用如有错误和不合理的地方务必批评指正~ 如果需要git源码可邮件给2260755767qq.com 再次感谢左大神对我算法的指点迷津
