如果按照简单的方式,逐个查找中间元素(往两边扩散),那么复杂度会是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;}
};