アルゴリズムの問題:配列は最も近い2つのサブ配列に分けます

アルゴリズムの問題:配列は最も近い2つのサブ配列に分けます
1つの配列を2つのサブ配列に分割し,サブ配列の和ができるだけ近づくことを要求する.
構想

配列を並べ替え、配列全体とを計算します.

区間和を計算します.最小要素から連続区間の和を計算し、和が配列と半分未満の場合、区間は右境界が右にシフトし、和が配列と半分以上の場合、区間は左境界が右にシフトします.区間と配列和の半分に最も近いとき,左右の境界の位置と区間和を記録した.区間と配列の半分に等しい場合、区間の要素は分割スキームのサブ配列であり、直接返されます.終了条件は、区間左境界が区間右境界より小さく、右境界が配列の最後の要素を超えないことです.

ぶんせき

             ，           。            ，                   。         ，      ，               ，           。

時間複雑度O(nlogn)O(nl o g n).空間複雑度O(n).
コード#コード#

vector<vector<int> > Leetcode::partitionNearestSumSubArr(const vector<int> &arr)
{
    if(arr.size()<2){
        return vector<vector<int> >({arr,vector<int>()});
    }

    vector<int> sortedArr=arr;
    SortAlgorithmn::quickSort(sortedArr);

    int sum=0;
    for(const auto& i : sortedArr) sum+=i;

    auto lClose=sortedArr.begin();
    auto rOpen=sortedArr.begin()+1;

    auto minDist=std::numeric_limits<int>::max();
    int curSum=*sortedArr.begin();
    for(auto i=sortedArr.begin(),j=sortedArr.begin()+1;iint curDist=curSum*2-sum;
        if(abs(curDist)abs(curDist);
            if(minDist == 0) break;
        }
        if(curDist>0){
            curSum-=(*i);
            ++i;
        }else if(curDist<0){
            curSum+=(*j);
            ++j;
        }else{
            lClose=i;
            rOpen=j;
            break;
        }
    }

    vector<int> first;
    first.assign(lClose,rOpen);
    sortedArr.erase(lClose,rOpen);;

    return vector<vector<int> >({first,sortedArr});
}

        stl    。
           。
              2，        2            。

完全なコードはgithubを参照してください.https://github.com/junbujianwpl/LeetcodePro.git
まとめ
最も近い問題については,クランプ法を用いることが考えられる.もちろんクランプ法はソートが必要です.
不連続区間については,頭加尾のように相補区間を求めることができる.