Medium

题目描述

给定一个整数 num，返回三个连续整数（作为排序数组），它们的和为 num。如果 num 不能表示为三个连续整数的和，返回一个空数组。

示例 1:

输入: num = 33
输出: [10,11,12]
解释: 33 可以表示为 10 + 11 + 12 = 33。
10, 11, 12 是 3 个连续整数，所以我们返回 [10, 11, 12]。

示例 2:

输入: num = 4
输出: []
解释: 没有办法将 4 表示为 3 个连续整数的和。

约束条件:

  • 0 <= num <= 10^15

提示:

  • 注意如果存在解，我们可以将它们表示为 x-1, x, x+1。这告诉我们关于这个数字的什么信息？
  • 注意数字的和将是 3x。你能求解 x 吗？

解题思路

这是一道数学题，核心思路是利用连续整数的性质。

设三个连续整数为 x-1, x, x+1，那么它们的和为：

(x-1) + x + (x+1) = 3x = num

因此，x = num / 3。

关键观察：

  1. 如果 num 能被 3 整除，那么 x = num / 3 是整数，三个连续整数为 [x-1, x, x+1]
  2. 如果 num 不能被 3 整除，则不存在三个连续整数的和等于 num

算法步骤：

  1. 检查 num 是否能被 3 整除
  2. 如果能整除，计算中间数 x = num / 3
  3. 返回 [x-1, x, x+1]
  4. 如果不能整除，返回空数组

时间复杂度分析： O(1) - 只需要常数时间的除法和判断操作 空间复杂度分析： O(1) - 只使用常数额外空间

代码实现

class Solution {
public:
    vector<long long> sumOfThree(long long num) {
        if (num % 3 != 0) {
            return {};
        }
        
        long long x = num / 3;
        return {x - 1, x, x + 1};
    }
};

class Solution:
    def sumOfThree(self, num: int) -> List[int]:
        if num % 3 != 0:
            return []
        
        x = num // 3
        return [x - 1, x, x + 1]

public class Solution {
    public long[] SumOfThree(long num) {
        if (num % 3 != 0) {
            return new long[0];
        }
        
        long x = num / 3;
        return new long[] {x - 1, x, x + 1};
    }
}

var sumOfThree = function(num) {
    if (num % 3 !== 0) {
        return [];
    }
    
    const x = Math.floor(num / 3);
    return [x - 1, x, x + 1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(1)只需要常数时间的除法和取模操作
空间复杂度O(1)只使用常数额外空间，返回数组不计入空间复杂度

相关题目