力扣209题：双指针和暴力解最小子数组

张开发
• 2026/4/16 20:49:15 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

力扣209题：双指针和暴力解最小子数组
一、题目要求力扣第209题给定一个含有n个正整数的数组和一个正整数target。找出该数组中满足其总和大于等于target的长度最小的子数组[numsl, numsl1, ..., numsr-1, numsr]并返回其长度。如果不存在符合条件的子数组返回0。二、代码实现暴力和双指针方式实现暴力双for循环遍历int minSubArrayLen(int target, int* nums, int numsSize) { int minnumsSize1,len; for(int i0;inumsSize;i){ int sum0; for(int ji;jnumsSize;j){ sumnums[j]; if(sumtarget){ lenj-i1; if(lenmin){ minlen; } } } } return minnumsSize1 ? 0:min; }双指针单for循环int minSubArrayLen(int target, int* nums, int numsSize) { int sum0; int minlennumsSize1,len; int i0; for(int j0;jnumsSize;j){ sumnums[j]; while(sumtarget){ len j-i1; if(lenminlen){ minlen len; } sum sum - nums[i]; i; } } return minlennumsSize1 ? 0:minlen; }三、核心思路暴力解法就是用两个for循环将所以子数组可能性都实现一边最终找出最小的子数组这个方式的好处就是更容易理解但是时间复杂度大遇到较大数据就会消耗更多时间而双指针解法就是相当于在数组里装一个可以随时变化的滑动窗口时间复杂度小。四、过程难点和总结双指针解法最主要的就是明白头尾指针的确定如何去移动起始位置的指针。如果把for循环条件的变量设置成起始位置的指针的话那么在起始指针移动一次结尾指针都要遍历一次数组这样就和暴力解法没有差别了所以应该将条件里的变量设置成结尾指针当子数组满足条件的时候起始位置指针向前移动并且把移动前位置的值减去这样就形成了一个滑动窗口很大程度的减小了时间复杂度。

更多文章