hazel'blog
0%

代码随想录第四天

发表于 更新于 分类于
本文字数： 980 阅读时长 ≈ 1 分钟

数组-长度最小的子数组

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int result = nums.size()+1;
        int sum = 0;
        int length = 0;
        for(int i = 0; i < nums.size(); i++){
            sum = 0;
            for(int j = i; j < nums.size(); j++){
                sum += nums[j];
                if(sum >= target){
                    length = j-i+1;
                    result = result < length ? result : length;
                    break;
                }
            }
        }
        return result == nums.size()+1 ? 0 : result;
    }
};

上面又是暴力的方法，复杂度O(n^2),使用双指针试试，设定两个指针left 和right分别为子数组的开始和结束位置，最开始都为0，每一轮迭代都将nums[right]加到sum中，如果sum>=target,那么就更新子数组长度以及将nums[left]移出sum,并将nums[left]右移，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int result = nums.size()+1;
        int sum = 0;
        int length = 0;
        int left = 0;
            for(int right = left; right < nums.size(); right++){
                sum += nums[right];
                while(sum >= target){
                    length = right-left+1;
                    result = result < length ? result : length;
                    sum -= nums[left++];
                }
            }
        
        return result == nums.size()+1 ? 0 : result;
    }
};