难度: Easy
给你一个整数 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
难度: Easy
给你一个整数 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
运行时间: 21 ms
内存: 16.0 MB
class Solution: def sumZero(self, n: int) -> List[int]: ans = [] if n % 2 == 0: for i in range(1, n//2 + 1): ans.append(i) ans.append(-i) else: ans.append(0) for i in range(1, n//2 + 1): ans.append(i) ans.append(-i) return ans
该题解的核心思想是通过平衡正负数来确保总和为零。对于偶数n,生成从1到n/2的正整数和它们的负数对。如果n是奇数,中间加入0,然后同样生成从1到n/2的正负数对。这样构造的数组长度恰好为n,并且所有元素的和为0。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution: def sumZero(self, n: int) -> List[int]: ans = [] # 初始化结果数组 if n % 2 == 0: for i in range(1, n//2 + 1): # 生成n/2对正负数 ans.append(i) # 添加正数 ans.append(-i) # 添加对应的负数 else: ans.append(0) # n为奇数时,在数组中添加0 for i in range(1, n//2 + 1): # 同样生成n/2对正负数 ans.append(i) # 添加正数 ans.append(-i) # 添加对应的负数 return ans # 返回结果数组
当n为奇数时,我们需要一个额外的数字来保持数组总和为零,因为仅使用正负数对的数量会少一个。例如,当n=3时,可以使用+1和-1,但仍然缺一个数字来达到3个元素的要求,添加0可以解决这个问题。而n为偶数时,正负数对的数量正好等于n,不需要添加0。
在这个特定的问题中,改变生成数的范围或顺序不会提升算法的性能,因为算法的复杂度主要由n决定,独立于生成数的具体范围。然而,改变数的范围或顺序可以增加结果的多样性。例如,可以从一个非零起始值开始生成正负数对,或者在输出数组中随机化正负数对的顺序,以生成不同的满足条件的数组。
是的,无论n是奇数还是偶数,正负数对的生成循环总是执行n/2次,因为我们需要生成n/2对正负数来保证总和为零。当n为奇数时,添加0并不需要额外的循环,因为0已经在循环外单独添加了,因此循环的数量并没有增加。
这种方法在n=1或n=1000等边界情况下仍然有效。对于n=1,只需要添加0,因为这是唯一的数字使得总和为零。对于n=1000,该方法通过生成500对正负数来保证总和为零,无论输入大小如何,这种方法的逻辑保持一致且有效。