力扣1477. 找两个和为目标值且不重叠的子数组

力扣1477. 找两个和为目标值且不重叠的子数组

题目解析及思路

题目要求找到两个互不重叠的子数组和都等于target的子数组长度和的最小值

暴力思路(差不多nlogn)：将所有子数组和等于target的子数组用map存起来下标

• 双指针枚举，如果有重叠就跳过，直到找到符合要求的就是最小值

代码

class Solution {
public:
    int minSumOfLengths(vector<int>& arr, int target) {
        //如果整个数组的和都比2倍target小，说明不可能分成两部分
        if(accumulate(arr.begin(),arr.end(),0LL) < target * 2) 
            return -1;
        //multimap可以存多个相同键值的对组，并且默认升序排列
        multimap<int,int> res;
        int l = 0,r = 0,sum = 0;
        //双指针求子数组和，把所有符合要求的子数组的{长度,下标}存入表中
        while(r < arr.size())
        {
            sum += arr[r];
            r ++;
            if(sum < target) continue;
            while(sum > target)
            {
                sum -= arr[l];
                l ++;
            }
            if(sum == target)
                res.insert({r-l,l});
        }
        int ans = INT_MAX;
        //枚举表中数据
        for(auto r1 = res.begin();r1 != res.end();r1 ++)
        {
            //剪枝，因为multimap默认升序，因此r1->first <= r2->first
            if(r1->first * 2 >= ans) break;
            auto r2 = r1;
            while((++r2) != res.end())
            {
                //判断是否有重叠
                if (r1->second < r2->second && r1->second + r1->first > r2->second) continue;
                if (r2->second < r1->second && r2->second + r2->first > r1->second) continue;
                //如果没重叠，当前答案一定是最优解(两个都是最小)
                ans = min(ans,r1->first+r2->first);
                break;
            }
        }
        return ans == INT_MAX ? -1 : ans;
    }
};

原文地址：https://blog.csdn.net/Pisasama/article/details/142870635

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！