Repository navigation
[LeetCode] 1304. Find N Unique Integers Sum up to Zero #1304
Description
Given an integer n, return any array containing n unique integers such that they add up to 0.
Example 1:
Input: n = 5
Output: [-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 = 3
Output: [-1,0,1]
Example 3:
Input: n = 1
Output: [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 打赏
---|---
Activity
[-][LeetCode] 1304. Missing Problem[/-][+][LeetCode] 1304. Find N Unique Integers Sum up to Zero[/+]