1304. Find N Unique Integers Sum up to Zero

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:

• 1 <= n <= 1000

💡 Hint 1:
Return an array where the values are symmetric. (+x , -x).

💡 Hint 2:
If n is odd, append value 0 in your returned array.

Submitted Code

class Solution:
    def sumZero(self, n: int) -> List[int]:
        val = n       # 유니크한 값
        result = []

        for i in range(0, n, 2):
            if i == n-1:            # n이 홀수일 경우 마지막 값 0
                result.append(0)
            else:
                result.append(-val) # -x, x 순으로 넣기
                result.append(val)
                val -= 1

        return result

Runtime: 0 ms | Beats 100.00%
Memory: 19.44 MB | Beats 17.11%

큰 수부터 (-x, x) 쌍으로 넣어서 항상 부분합이 0이 되도록 유지했다. n이 홀수면 마지막에 0을 하나 추가하면 된다.

n = 5

[-5,  5]               -> sum = 0
[-5,  5, -4,  4]       -> sum = 0
[-5,  5, -4,  4,  0]   -> sum = 0

return [-5, 5, -4, 4, 0]

Other Solutions

1st

class Solution(object):
    def sumZero(self, n):
        return range(1 - n, n, 2)

time complexity: 𝑂(𝑛)
space complexity: 𝑂(𝑛)

리트코드에서는 리스트가 아니어도 iterable 값이면 정답으로 인정되기 때문에 range() 만으로도 풀 수 있다. 이 나열은 수학적으로 항상 쌍대칭이기 때문에 전체 합이 항상 0이 된다.

2nd

class Solution:
    def sumZero(self, n: int) -> List[int]:
        return [ n * (1 - n) // 2] + list(range(1, n))

무조건 쌍대칭이 되도록 값을 나열하지 않아도 된다. 이 코드는 1부터 n-1까지의 값을 먼저 넣고, 그 합을 정확히 0으로 만들어주는 마지막 음수 값 하나를 맨 앞에 붙여서 보정하는 방법을 사용해다.