您的位置:首页 > 汽车 > 时评 > 黄山网络推广哪家好_网站制作的公司有哪些_株洲24小时新闻_seo营销

黄山网络推广哪家好_网站制作的公司有哪些_株洲24小时新闻_seo营销

2024/11/17 21:29:12 来源:https://blog.csdn.net/coldasice342/article/details/143633058  浏览:    关键词:黄山网络推广哪家好_网站制作的公司有哪些_株洲24小时新闻_seo营销
黄山网络推广哪家好_网站制作的公司有哪些_株洲24小时新闻_seo营销


这段代码实现了一个解决“长度最小的子数组”问题的Java解决方案,采用了滑动窗口的算法思想。下面是详细的中文解释:

算法思想:

  1. 滑动窗口:该算法利用了滑动窗口的思想,窗口的左右边界分别用变量 leftright 来表示。right 向右移动遍历数组中的每个元素,不断扩大窗口,直到窗口内的元素和达到或超过目标值 target

  2. 窗口内求和:我们定义了一个 sum 变量来记录当前窗口内元素的和。每当 right 向右移动时,将当前 nums[right] 的值加入到 sum 中。

  3. 缩小窗口:当 sum 达到或超过 target 时,表示当前窗口(从 leftright)满足条件,即窗口内的元素和大于等于 target。这时候,我们尝试通过增大 left 的值来缩小窗口,从而找到符合条件的最小长度子数组。

    • 在缩小窗口时,我们每次计算当前窗口的长度,并更新 minLengthminLength 和当前窗口长度之间的最小值。
    • 然后,从 sum 中减去 nums[left] 的值,并将 left 向右移动一个位置,以继续寻找更小的符合条件的子数组。
  4. 最终结果:遍历完整个数组后,如果 minLength 仍然是初始值 Integer.MAX_VALUE,说明没有找到符合条件的子数组,返回 0。否则,返回 minLength,即符合条件的最小子数组的长度。

时间复杂度:

该算法的时间复杂度为 (O(n)),因为每个元素最多被处理两次(一次是被 right 指针添加进窗口,另一次是被 left 指针移出窗口)。

总结:

  • 使用滑动窗口逐步扩大和缩小窗口,确保在满足条件的同时,找到最小长度的子数组。
  • 如果不存在满足条件的子数组,返回 0;否则返回最小长度。

java solution

class Solution {public int minSubArrayLen(int target, int[] nums) {int left = 0;int sum = 0; //初始化窗口内的和int minLen = Integer.MAX_VALUE;//右边界遍历数组for(int right = 0; right < nums.length; right++) {//逐渐尝试求和sum += nums[right];//当 sum >= target 时,尝试缩小窗口while(sum >= target) {minLen = Math.min(minLen, right - left + 1);sum -= nums[left];//将左边界的值从sum中减去left++; //移动左边界,缩小窗口}}return minLen == Integer.MAX_VALUE ? 0 : minLen;}
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com