Leetcode 1477. 找两个和为目标值且不重叠的子数组（DAY 188）---- 二分查找学习期

叁歲伎倆 2022-09-15 12:44 90阅读 0赞

### 文章目录 ###

*   *  原题题目
     *  代码实现（首刷自解）

--------------------

## 原题题目 ##

--------------------

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]

--------------------

## 代码实现（首刷自解） ##

--------------------

class Solution { 
    public:
        int my_upper_bound(vector<pair<int,int>>& v,int left,int right,int target)
        { 
            while(left < right)
            { 
                int mid = (left + right)/2;
                if(v[mid].first >= target)    right = mid;
                else left = mid + 1;
            }
            return left;
        }
    
        int minSumOfLengths(vector<int>& arr, int target) { 
            vector<pair<int,int>> v; 
            int left = 0,right = 0,tmpsum = 0,ret = INT_MAX;
    
            while(right < arr.size())
            { 
                while(right < arr.size() && tmpsum <= target)
                { 
                    tmpsum += arr[right++];
                    if(tmpsum == target)
                        v.emplace_back(left,right);
                }
    
                while(tmpsum >= target)
                { 
                    tmpsum -= arr[left++];
                    if(tmpsum == target)
                        v.emplace_back(left,right);
                }
            }
            if(v.size() < 2)    return -1;
            sort(v.begin(),v.end());
            vector<int> dp(v.size(),INT_MAX);
            for(int i=dp.size()-1;i>=0;--i)
            { 
                if(i == dp.size()-1) dp[i] = v[i].second - v[i].first;
                else dp[i] = min(v[i].second - v[i].first,dp[i+1]);
            }
    
            for(int i=0;i<v.size()-1;++i)
            { 
                int left = v[i].second - v[i].first; 
                auto pos = my_upper_bound(v,i+1,v.size(),v[i].second);
                if(pos != v.size()) 
                    ret = min(ret,dp[pos] + left);   
            }
            return ret == INT_MAX ? -1 : ret;
        }
    };

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/b3a2d786f42544dd82bad20c1b654818.png