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

原题链接： 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，前缀和为nummp[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;}
};