专栏首页算法修养LeetCode 209. Minimum Size Subarray Sum(DP)

LeetCode 209. Minimum Size Subarray Sum(DP)

题意:求一个数组里最短的连续子序列的和大于等于s的长度

题解:可以用动态规划,我就是用动态规划过的,但是确实不是最简单的解法,看了题解最简单的是双指针,

双指针

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        
        int sum=0;
        
        int left=0;
        
        int ans=INT_MAX;
        for(int i=0;i<nums.size();i++)
        {
            sum+=nums[i];
            while(sum>=s)
            {
                ans=min(ans,i-left+1);
                sum-=nums[left];
                left++;
            }
        }
        
        return ans==INT_MAX?0:ans;
        
    }
};

DP

class Solution {
public:
    int dp[100005];
    int dp2[100005];
    int minSubArrayLen(int s, vector<int>& nums) {
        
        int ans=INT_MAX;
        if(nums.size()==0)
            return 0;
        
        dp[0]=0;
        dp2[0]=nums[0];
        for(int i=1;i<nums.size();i++)
        {
            if(nums[i]+dp2[i-1]>=s)
            {
                int j=0;
                int sum=0;
                for(j=dp[i-1];j<=i-1;j++)
                {
                    sum+=nums[j];
                    if(nums[i]+dp2[i-1]-sum<s)
                    {
                        break;
                    }
                }
                
                dp[i] = j;
                dp2[i] = dp2[i-1] + nums[i] - sum + nums[j];
            }
            else
            {
                dp[i]=dp[i-1];
                dp2[i]=dp2[i-1]+nums[i];
            }
            
            if(dp2[i]>=s)
                ans=min(ans,i-dp[i]+1);
        }
        
        
        return ans==INT_MAX?0:ans;
        
    }
};

二者效率都是差不多的。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 217. Contains Duplicate

    ShenduCC
  • LeetCode 239. Sliding Window Maximum(Hard)

    题意:在一个固定长度的滑动窗口里,计算窗口里的最大值,并且这个滑动窗口每次移动一个。

    ShenduCC
  • LeetCode 45 Jump Game II

    这道题目乍一看,我以为是动态规划。可是LeetCode 从来不给数据范围。,又是hard难度的题目,所以我猜测数组长度至少10万吧。

    ShenduCC
  • leetcode哈希表之两数之和

    这里利用HashMap来存储目标值与当前值的差值及其索引,遍历nums数组,遇到存在的key则直接返回。

    codecraft
  • leetcode哈希表之两数之和

    这里利用HashMap来存储目标值与当前值的差值及其索引,遍历nums数组,遇到存在的key则直接返回。

    codecraft
  • Two Sum

    Given an array of integers, return indices of the two numbers such that they add...

    Tyan
  • Single Number III

    Tyan
  • 【Leetcode】53. 最大子序和

    给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 示例:

    Leetcode名企之路
  • 两数之和(TwoSum)

    我工作2年已经感觉到危机感,正准备同时这面临着两个问题了,不如蹭现在还有来得及一起去把算法练起来吧,光看可不行得练。尽可能的把 https://leetcode...

    爱敲代码的猫
  • 两数之和(TwoSum)

    我工作2年已经感觉到危机感,正准备同时这面临着两个问题了,不如蹭现在还有来得及一起去把算法练起来吧,光看可不行得练。尽可能的把 https://leetcode...

    爱敲代码的猫

扫码关注云+社区

领取腾讯云代金券