题目描述

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

样例

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

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

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

限制

• 1 <= n <= 1000

算法

(构造) $O(n)$

1. 如果 n 是奇数，则最后一个位置放 0。剩下偶数个位置，每次放一对相反数即可。

时间复杂度

• 每个位置遍历一次，故时间复杂度为 $O(n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储答案。

C++ 代码

class Solution {
public:
    vector<int> sumZero(int n) {
        vector<int> res(n);
        if (n & 1)
            res[n - 1] = 0;

        for (int i = 0; i < n / 2; i++) {
            res[i] = i + 1;
            res[i + n / 2] = -i - 1;
        }

        return res;
    }
};