LeetCode 网易-1. 分割环（前缀和 + 哈希）

文章目录

1. 题目2. 解题

1. 题目

小易有 n 个数字排成一个环，你能否将它们分成连续的两个部分(即在环上必须连续)，使得两部分的和相等？

输入描述：

第一行数据组数 T ，对于每组数据 第一行数字 n ，表示数字个数 接下来一行 n 个数，按顺序给出环上的数字。 2 <= n <= 100000, 1 <= Ai <= 10 ^ 9

输出描述： 对于每组数据，一行输出YES/NO

示例1: 输入 1 6 1 2 3 4 5 6 输出 NO 示例2: 输入 1 4 4 4 5 3 输出 YES

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/S0WXIw 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

#include<bits/stdc++.h> using namespace std; int main() { int T, n, a, i; cin >> T; while(T--) { cin >> n; vector<long long> arr(n, 0);//注意溢出 i = 0; while(n--) { cin >> a; if(i == 0) arr[i] = a; else arr[i] = arr[i-1] + a;//前缀和 i++; } if(arr.back()%2 != 0)//和不能被2整除，分不开 { cout << "NO" << endl; continue; } unordered_set<long long> s; long long half = arr.back()/2; bool yes = false; for(i = 0; i < arr.size(); ++i) { if(s.count(arr[i]-half)) { //前缀和减去half的值存在，即找到连续的和为half yes = true; break; } s.insert(arr[i]);//更新前缀和的集合 } if(yes) cout << "YES" << endl; else cout << "NO" << endl; } }

0 ms 3.2 MB

---

我的博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！