当前位置：首页 > article >正文

Leetcode 1477. 找两个和为目标值且不重叠的子数组前缀和+DP

article 2025/3/6 19:28:13

原题链接： Leetcode 1477. 找两个和为目标值且不重叠的子数组

在这里插入图片描述

class Solution {
public:
    int minSumOfLengths(vector<int>& arr, int target) {
        int n=arr.size();
        int sum=0;
        int maxn=INT_MAX;
        vector<int> dp(n,maxn);//dp[i]表示以索引i之前的满足要求的子数组的长度的最小值
        map<int,int> mp;//mp[num]=i,表示从0到i，前缀和为num
        mp[0]=-1;//初始时
        int res=maxn;
        for(int i=0;i<n;i++){
            sum+=arr[i];
            if(i>0) dp[i]=dp[i-1];
            if(mp.count(sum - target)){
                int cur_len=i-mp[sum-target];
                int left_index=mp[sum-target];
                if(left_index>=0 && dp[left_index]!=INT_MAX){
                    res=min(res,dp[left_index]+cur_len);
                }
                if(i==0) dp[i]=min(maxn,cur_len);
                else dp[i]=min(dp[i-1],cur_len);
            }
            mp[sum]=i;
        }
        if(res==maxn) return -1;
        return res;
    }
};