Description
Given an integer n, return any array containing n unique integers such that they add up to 0.
Example 1:
Input: n = 5
Output: [-7,-1,1,3,4]
Explanation: These arrays also are accepted [-5,-1,1,2,3] , [-3,-1,2,-2,4].
Example 2:
Input: n = 3
Output: [-1,0,1]
Example 3:
Input: n = 1
Output: [0]
Constraints:
Solutions
Solution 1: Construction
We can start from 1 and alternately add positive and negative numbers to the result array. We repeat this process n⁄2 times. If n is odd, we add 0 to the result array at the end.
The time complexity is O(n), where n is the given integer. Ignoring the space used for the answer, the space complexity is O(1).
PythonJavaC++GoTypeScriptRust
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(code-box)
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;
}
}(code-box)
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;
}
};(code-box)
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
}(code-box)
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;
}(code-box)
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
}
}(code-box)
Solution 2: Construction + Mathematics
We can also add all integers from 1 to n-1 to the result array, and finally add the opposite of the sum of the first n-1 integers, which is -n(n-1)⁄2, to the result array.
The time complexity is O(n), where n is the given integer. Ignoring the space used for the answer, the space complexity is O(1).
PythonJavaC++GoTypeScriptRust
class Solution:
def sumZero(self, n: int) -> List[int]:
ans = list(range(1, n))
ans.append(-sum(ans))
return ans(code-box)
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;
}
}(code-box)
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;
}
};(code-box)
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
}(code-box)
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;
}(code-box)
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
}
}(code-box)
