跳转至

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

来源第 169 场周赛 Q1难度简单分数1167

题目描述

给你一个整数 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

解法

方法一：构造

思考

需要 \(n\) 个互不相同且和为 \(0\) 的整数。随机选取后再调整容易破坏互异性。互为相反数的一对已经和为 \(0\)，因此放入 \(1,-1,\ldots,k,-k\)。若 \(n\) 为奇数，再补一个 \(0\)，和与互异性同时成立。

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

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

1
2
3
4
5
6
7
8
9
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
    }
};

1
2
3
4
5
6
7
8
9
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
}

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
impl Solution {
    pub fn sum_zero(n: i32) -> Vec<i32> {
        let mut ans = vec![0; n as usize];
        let mut j = 0;
        for i in 1..=n / 2 {
            ans[j] = i;
            j += 1;
            ans[j] = -i;
            j += 1;
        }
        ans
    }
}

方法二：构造 + 数学

思考

成对构造需要处理奇偶。将 \(1\) 到 \(n-1\) 直接放入，最后一项取前 \(n-1\) 项之和的相反数，和必为 \(0\)，且该项不等于已有任一正整数。写法更短，仍保证互异。

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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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;
    }
}

1
2
3
4
5
6
7
8
9
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;
    }
};

1
2
3
4
5
6
7
8
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
}

1
2
3
4
5
6
7
8
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
impl Solution {
    pub fn sum_zero(n: i32) -> Vec<i32> {
        let mut ans = vec![0; n as usize];
        for i in 1..n {
            ans[i as usize] = i;
        }
        ans[0] = -(n * (n - 1) / 2);
        ans
    }
}

评论