连续环状数组问题.md

连续环状数组问题

对于环状数组，最为头疼的就是到达右端时，需要拼接左端的数组，比如刚做的一道网易测试笔试题：有n个数字排成一个环，能否将它们分成连续的两部分，使得两部分和相等。

举一个例子来说，1，3，5，3，4就是可以的，因为分成[5,3]和[4,1,3]即可，和均为8。

当然，3，5，4，4也是可以的，这个特例是不需要跨数字的，直接为[3,5]和[4,4]，和均为8。

因为该问题的关键就是当我们将其分为两部分时，跨越了右边界如何处理。

• 借鉴了一道题，说的是将字符串左移几位后，左边移出的位补到右边，有一种方法是复制该字符串，再去移动，这样就不需要考虑移出的字符问题了。

  • 比如string左移2位，得到ringst，我们只需复制一次，拼接到右边，得到stringstring，然后使用substr即可，s.substr(2,len)
  • 本质上，这也形成了一个环的问题

• 对于本题，我们也使用了这样的思路，当然前面做一步处理，就是先保存整个数组的和，这样，只要去计算其中一部分就可以得到另一部分的和。使用accumulate(iterator1,iterator2,init)函数，分别表示需要计算的起始、终点迭代器以及初始值，一般为0。

• 接着就是把数组复制一遍放到后面。这里用了vector的特性，vec.insert(iterator,beg,end)，表示插入的位置，需要插入的数组的起始和末尾迭代器。

  于是，1，3，5，3，4就变成了1，3，5，3，4，1，3，5，3，4

• 然后遍历第一部分的长度d，d从1到n-1。

• 对于每个长度d，我们都去计算该长度的和，需要计算n次，再次使用accumulate函数即可。但是这里的起始和终点分别为s，s+d。

• 最后就是比较两部分的和是否相等

代码如下：

bool isEqual(vector<int>&vec, int n)
{
    vector<int> res = vec;
    res.insert(res.end(), vec.begin(), vec.end());//因为是环状，所以先把它设置成两倍
    int allsum = accumulate(vec.begin(), vec.end(), 0);
    for (int d = 1; d < n; d++) {//第一段的长度
        for (int s = 0; s < n; s++) {//以这段长度遍历所有的情况
            int sum_1 = accumulate(res.begin() + s, res.begin() + s + d, 0);
            if (allsum - sum_1 == sum_1) {//如果第一段与另一端相等
                return true;
            }
        }
    }
    return false;
}
int main()
{
    int n;
    cin >> n;
    vector<int> res;
    for (int i = 0; i < n; i++)
    {
        int tmp;
        cin >> tmp;
        res.push_back(tmp);
    }
    if (isEqual(res, n))
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    return 0;
}

总结：连续的环状问题，可以在原始数组后面再添加原数组，方便处理。