每日一题（leetcode2909）：单份查找与群组查找

如果按照简单的方式，逐个查找中间元素（往两边扩散），那么复杂度会是n方。

这种方式没有对比较大小后的数据进行充分利用，所以复杂度较高。

我们考虑到既然要遍历，那么不妨干脆先把所有元素的左边最小值和右边最小值都计算出来，这样可以最大的有效利用比较方式。即创建左边最小数据和右边最小数据，最终配合原数组和条件语句便可以计算出结果，复杂度3n的样子。代码如下：

class Solution {
public:
    int minimumSum(vector<int>& nums) {
        int minres=300001000;
        int l=nums.size();
        vector<int> left;
        vector<int> right;
        left.push_back(minres);
        right.push_back(minres);
        int min1=nums[0];
        int min2=nums[l-1];

        for(int i=0;i<l-1;i++)
        {
            if(nums[i]<min1) {min1=nums[i];}            
            left.push_back(min1);
        }

        for(int i=l-1;i>0;i--)
        {
            if(nums[i]<min2) {min2=nums[i];}            
            right.push_back(min2);
        }
        int k=0;
        for(int i=1;i<l-1;i++)
        {
            if(nums[i]>left[i] && nums[i]>right[l-1-i])
            {
                k=1;
                if (nums[i]+left[i]+right[l-1-i]<minres)
                {minres=nums[i]+left[i]+right[l-1-i];}
            }
        }
        if (k==0)
        {minres=-1;}
        
        return minres;
    }
};