Question

1304. 和为零的 N 个不同整数

English Version

题目描述

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

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

• 1 <= n <= 1000

解法

方法一：构造

我们可以从 $1$ 开始，依次将正数和负数交替放入结果数组中，一共循环 $\frac{n}{2}$ 次，如果 $n$ 为奇数，则最后再将 $0$ 放入结果数组中。

时间复杂度 $O(n)$，其中 $n$ 为给定的整数。忽略答案的空间消耗，空间复杂度 $O(1)$。

class Solution:
  def sumZero(self, n: int) -> List[int]:
    ans = []
    for i in range(n >> 1):
      ans.append(i + 1)
      ans.append(-(i + 1))
    if n & 1:
      ans.append(0)
    return ans

class Solution {
  public int[] sumZero(int n) {
    int[] ans = new int[n];
    for (int i = 1, j = 0; i <= n / 2; ++i) {
      ans[j++] = i;
      ans[j++] = -i;
    }
    return ans;
  }
}

class Solution {
public:
  vector<int> sumZero(int n) {
    vector<int> ans(n);
    for (int i = 1, j = 0; i <= n / 2; ++i) {
      ans[j++] = i;
      ans[j++] = -i;
    }
    return ans;
  }
};

func sumZero(n int) []int {
  ans := make([]int, n)
  for i, j := 1, 0; i <= n/2; i, j = i+1, j+1 {
    ans[j] = i
    j++
    ans[j] = -i
  }
  return ans
}

function sumZero(n: number): number[] {
  const ans = new Array(n).fill(0);
  for (let i = 1, j = 0; i <= n / 2; ++i) {
    ans[j++] = i;
    ans[j++] = -i;
  }
  return ans;
}

方法二：构造 + 数学

我们也可以将 $1$ 到 $n-1$ 的所有整数放入结果数组中，最后再把前 $n-1$ 个整数的和 $\frac{n(n-1)}{2}$ 的相反数放入结果数组中。

时间复杂度 $O(n)$，其中 $n$ 为给定的整数。忽略答案的空间消耗，空间复杂度 $O(1)$。

class Solution:
  def sumZero(self, n: int) -> List[int]:
    ans = list(range(1, n))
    ans.append(-sum(ans))
    return ans

class Solution {
  public int[] sumZero(int n) {
    int[] ans = new int[n];
    for (int i = 1; i < n; ++i) {
      ans[i] = i;
    }
    ans[0] = -(n * (n - 1) / 2);
    return ans;
  }
}

class Solution {
public:
  vector<int> sumZero(int n) {
    vector<int> ans(n);
    iota(ans.begin(), ans.end(), 1);
    ans[n - 1] = -(n - 1) * n / 2;
    return ans;
  }
};

func sumZero(n int) []int {
  ans := make([]int, n)
  for i := 1; i < n; i++ {
    ans[i] = i
  }
  ans[0] = -n * (n - 1) / 2
  return ans
}

function sumZero(n: number): number[] {
  const ans = new Array(n).fill(0);
  for (let i = 1; i < n; ++i) {
    ans[i] = i;
  }
  ans[0] = -((n * (n - 1)) / 2);
  return ans;
}