[LeetCode] 1304. Find N Unique Integers Sum up to Zero

[grandyang]

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 同步地址:

#1304

参考资料：

https://leetcode.com/problems/find-n-unique-integers-sum-up-to-zero/

https://leetcode.com/problems/find-n-unique-integers-sum-up-to-zero/discuss/463890/Simple-Java-%3A-Fill-from-both-sides

https://leetcode.com/problems/find-n-unique-integers-sum-up-to-zero/discuss/465585/JavaC%2B%2BPython-Find-the-Rule

https://leetcode.com/problems/find-n-unique-integers-sum-up-to-zero/discuss/463998/Keep-it-simple.-Add-all-values-till-n-1-and-then-balance-it-with-sum.

LeetCode All in One 题目讲解汇总(持续更新中...)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

喜欢请点赞，疼爱请打赏❤️~.~

微信打赏

|

Venmo 打赏

---|---