Uh oh!
There was an error while loading.Please reload this page.
- Notifications
You must be signed in to change notification settings - Fork739
Description
Given an integer n, return any array containing n unique integers such that they add up to 0.
Example 1:
Input: n = 5Output: [-7,-1,1,3,4]Explanation: These arrays also are accepted [-5,-1,1,2,3] , [-3,-1,2,-2,4].Example 2:
Input: n = 3Output: [-1,0,1]Example 3:
Input: n = 1Output: [0]Constraints:
1 <= n <= 1000
这道题给了一个正整数n，让返回一个长度为n的数组，要求是没有重复数字且数字之和为0。博主最先想到的办法就是根据数组的个数来做不同的处理，若n为偶数，说明数组正好可以平均分为两段，这样从1开始，加个1，加个 -1，然后加个2，加个 -2，都相互抵消了，凑够n/2 对儿就可以了。若n为奇数，只要多加个0进去，既不会重复，又不会影响数字之和，就可以完成题目的要求了，参见代码如下：
解法一：
class Solution {public: vector<int> sumZero(int n) { vector<int> res; int half = n / 2; if (n % 2 != 0) res.push_back(0); for (int i = 1; i <= half; ++i) { res.push_back(i); res.push_back(-i); } return res; }};再来看一种很类似的解法，这种是在数组的两端往中间更新，新建一个大小为n的数组，初始化均为0，两端分别赋值为1和 -1，然后往中间一步，赋值为2和 -2，直到中间的位置。若最中间只有一个数字，则保持为0不变，不会产生重复也不影响数字和，参见代码如下：
解法二：
class Solution {public: vector<int> sumZero(int n) { vector<int> res(n); int left = 0, right = n - 1, start = 1; while (left < right) { res[left++] = start; res[right--] = -start; ++start; } return res; }};再来看一种方法，从数组的第二个数字开始赋值为 1，2，3...，然后第一个位置放后面所有数字之和的相反数，这样整个数组和还是0，同样也可以达到要求，参见代码如下：
解法三：
class Solution {public: vector<int> sumZero(int n) { vector<int> res(n); for (int i = 1; i < n; ++i) { res[i] = i; res[0] -= i; } return res; }};Github 同步地址:
参考资料：
https://leetcode.com/problems/find-n-unique-integers-sum-up-to-zero/
LeetCode All in One 题目讲解汇总(持续更新中...)
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）
微信打赏
Venmo 打赏
---|---
