CTF of Z2BNS
0%

和为零的N个唯一整数

发表于 分类于 ，
| 阅读次数： |
Valine：
本文字数： 801 阅读时长 ≈ 1 分钟

题目地址

难度：⭐

题目描述：

给你一个整数 n，请你返回 任意 一个由 n 个 各不相同 的整数组成的数组，并且这 n 个数相加和为 0 。

示例1：

1
2
3
输入：n = 5
输出：[-7,-1,1,3,4]
解释：这些数组也是正确的 [-5,-1,1,2,3]，[-3,-1,2,-2,4]。

示例2：

1
2
输入：n = 3
输出：[-1,0,1]

示例3：

1
2
输入：n = 1
输出：[0]

提示：

  • 1 <= n <= 1000
🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️解题过程🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️
解题过程：

思路：

多种做法

方法一：可以把前面几个数加起来，最后一个数取之前所有元素和的相反数，

方法二：同时放入每个数和它的相反数，注意奇数时要放入0

c++代码：(执行用时4ms，击败43.73%，内存消耗7M，击败14.56%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> sumZero(int n) {
        vector<int> result;
        //n为奇数,数组中放入0
        if(n%2!=0){
            result.push_back(0);
        }
        //放入整数和它的相反数
        for(int i=1;i<n/2+1;++i){
            result.push_back(i);
            result.push_back(i*-1);
        }
        return result;
    }
};
💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎官 方 题 解💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎
官方题解:

方法一：构造
我们首先将最小的 n - 1 个自然数 0, 1, 2, ..., n - 2 放入数组中，它们的和为 sum。对于剩下的 1 个数，我们可以令其为 -sum，此时这 n 个数的和为 0，并且：

当 n = 1 时，我们构造的答案中只有唯一的 1 个数 0；

当 n > 1 时，我们构造的答案中包含 n - 1 个互不相同的自然数和 1 个负数；

因此这 n 个数互不相同，即我们得到了一个满足要求的数组。

c++代码：(执行用时4ms，击败43.73%，内存消耗6.9M，击败20.06%）

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> sumZero(int n) {
        vector<int> ans;
        int sum = 0;
        for (int i = 0; i < n - 1; ++i) {
            ans.push_back(i);
            sum += i;
        }
        ans.push_back(-sum);
        return ans;
    }
};

复杂度分析

  • 时间复杂度：$O(N)$。
  • 空间复杂度：$O(1)$，除了存储答案的数组 ans 之外，额外的空间复杂度是 $O(1)$。
⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总 结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳
总结：

官方题解就是我思路里的第一种解法，哈哈哈😁，我使用的是第二种。还有就是c++可以直接在整数前加’-‘取相反数。

------------- THE END! THANKS! -------------