长度最小的子数组
第一次自己答
超出时间范围，时间复杂度太高
#include <iostream> #include <vector> using namespace std; class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int sum = 0, size=0,subsize=0 ; for (int j = 0; j < nums.size(); j++) { for (int i = j; i < nums.size(); i++) { sum += nums[i]; size++; if (sum >= target) { if (subsize == 0) subsize = size; else if (size < subsize) { subsize = size; } size = 0; sum = 0; } } size = 0; sum = 0; } return subsize; } }; int main() { vector<int> my_nums = { 1,2,3,4,5}; int target = 15; Solution a; cout << a.minSubArrayLen(target , my_nums); return 0; }
暴力解法
和自己写的原理类似，都是超时
#include <iostream> #include <vector> using namespace std; class Solution { public: int minSubArrayLen(int s, vector<int>& nums) { int result = INT32_MAX; // 最终的结果 int sum = 0; // 子序列的数值之和 int subLength = 0; // 子序列的长度 for (int i = 0; i < nums.size(); i++) { // 设置子序列起点为i sum = 0; for (int j = i; j < nums.size(); j++) { // 设置子序列终止位置为j sum += nums[j]; if (sum >= s) { // 一旦发现子序列和超过了s，更新result subLength = j - i + 1; // 取子序列的长度 result = result < subLength ? result : subLength; break; // 因为我们是找符合条件最短的子序列，所以一旦符合条件就break } } } // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列 return result == INT32_MAX ? 0 : result; } }; int main() { vector<int> my_nums = { 2,3,1,2,4,3 }; int target = 7; Solution a; cout << a.minSubArrayLen(target , my_nums); return 0; }
滑动窗口 （双指针）
#include <iostream> #include <vector> using namespace std; class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int i = 0, sum = 0, length = 0, result = INT32_MAX; for (int j = 0; j < nums.size(); j++) { sum += nums[j]; while (sum >= target) { length = j - i + 1; result = result < length ? result : length; sum -= nums[i++]; } } return result ==INT32_MAX ? 0:result; } }; int main() { vector<int> my_nums = { 2,3,1,2,4,3 }; int target = 7; Solution a; cout << a.minSubArrayLen(target , my_nums); return 0; }
二刷
class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int result=INT_MAX ,sum=nums[0]; int left=0,right=0; for(right=0 ; right<nums.size() && left<=right;) { if( sum >= target ) { if( right-left+1 <= result) result = right-left+1 ; cout<<left<<' '<<right<<' '<<sum<<endl; sum -= nums[left]; left++; }else { right++; if(right>=nums.size()) break; sum += nums[right]; } } if(result == INT_MAX) return 0; return result; } };
