算法（42）-数组等值切割-前缀累加和-哈希表Map-set版-C++

题目：给定正整数，返回该数组能不能分成4部分，且每个部分累加和相等。切分位置的数不要。
比如：arr[]=[3,2,4,1,4,9,5,10,1,2,2] 返回 true
           三个切割点下标为2,5,7.[3 2][1 4] [5] [1 2 2]

思路：预处理结构技巧，前缀累加和模型。
           set和map两种哈希表类型。其实没啥本质差别。
1.unordered_set版
 

bool canSplits_set(vci arr) 
{
    if (arr.size() < 7) 
    {
        return false;
    }
    unordered_set <string> myset;                  //1.预处理结构
    int sum = 0;
    for (int i = 0; i < arr.size(); i++)          //2.预处理 得到累加和
    {
        sum += arr[i];                            //累加和计算
    }
    int leftSum = arr[0];
    for (int i = 1; i < arr.size() - 1; i++)    //3.放入 key 为 value index
    {
        string str = to_string(leftSum) + "_" + to_string(sum - leftSum - arr[i]);
        myset.insert(str);
        leftSum += arr[i];
    }
    int l = 1;
    int lsum = arr[0];     
    int r = arr.size() - 2;
    int rsum = arr[arr.size() - 1];
    while (l < r - 3)
    {
        if (lsum == rsum) 
        {
            string lkey = to_string(lsum * 2 + arr[l]);
            string rkey = to_string(rsum * 2 + arr[r]);
            if (myset.count(lkey + "_" + rkey))
            {
                return true;
            }
            lsum += arr[l++];
        }
        else if (lsum < rsum) {
            lsum += arr[l++];
        }
        else {
            rsum += arr[r--];
        }
    }
    return false;
}

2.unordered_map版

bool canSplits_map(vci arr) 
{
    if (arr.size() < 7)
    {
        return false;
    }
    unordered_map <int, int> mymap;//1.预处理结构
    int sum = arr[0];//1.0
    for (int i = 1; i < arr.size(); i++)             //2.预处理 得到累加和
    {
        mymap.insert(make_pair(sum, i));
        sum += arr[i];                               //累加和计算
    }

    int lsum = arr[0];                            //第一刀左侧的累加和
    for (int s1 = 1; s1 < arr.size() - 5; s1++) 
       {
        int checkSum = lsum * 2 + arr[s1];        //3.s1第一刀的位置 从1开始试  第一刀不会过右的
        if (mymap.count(checkSum))            //第2刀
        {
            int s2 = mymap.find(checkSum)->second;                    
            checkSum += lsum + arr[s2];
            if (mymap.count(checkSum))
            {
                int s3 = mymap.find(checkSum)->second;
                if (checkSum + arr[s3] + lsum == sum)//第3刀和最后的累加和对上
                {
                    return true;
                }
            }
        }
        lsum += arr[s1];
    }
    return false;
}

3.主程序调用

void canSplit_main() 
 {
     cout << "***********canSplit_main**********" << endl;
     vci vci1;
     vci1.insert(vci1.begin(), { 3, 2, 4, 1, 4, 9, 5, 10, 1, 2, 2 });
     cout << "arr[3, 2, 4, 1, 4, 9, 5, 10, 1, 2, 2]   canSplits_set  返回true---"  << canSplits_set(vci1) << endl;

     cout << "arr[3, 2, 4, 1, 4, 9, 5, 10, 1, 2, 2]   canSplits_map  返回true---" << canSplits_map(vci1) << endl;
}