LeetCode 题解工作台
找出数组的串联值
给你一个下标从 0 开始的整数数组 nums 。 现定义两个数字的 串联 是由这两个数值串联起来形成的新数字。 例如， 15 和 49 的串联是 1549 。 nums 的 串联值 最初等于 0 。执行下述操作直到 nums 变为空： 如果 nums 的长度大于 1，分别选中 nums 中的第一个元…
3
题型
7
代码语言
3
相关题
当前训练重点
简单 · 双·指针·invariant
答案摘要
从数组两端开始，每次取出一个元素，将其与另一个元素拼接，然后将拼接后的结果加到答案中。重复这个过程，直到数组为空。 时间复杂度 $O(n \times \log M)$，空间复杂度 $O(\log M)$。其中 和 分别是数组的长度和数组中的最大值。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 双·指针·invariant 题型思路
题目描述
给你一个下标从 0 开始的整数数组 nums 。
现定义两个数字的 串联 是由这两个数值串联起来形成的新数字。
- 例如，
15和49的串联是1549。
nums 的 串联值 最初等于 0 。执行下述操作直到 nums 变为空：
- 如果
nums的长度大于 1，分别选中nums中的第一个元素和最后一个元素，将二者串联得到的值加到nums的 串联值 上，然后从nums中删除第一个和最后一个元素。例如，如果nums是[1, 2, 4, 5, 6]，将 16 添加到串联值。 - 如果
nums中仅存在一个元素，则将该元素的值加到nums的串联值上，然后删除这个元素。
返回执行完所有操作后 nums 的串联值。
示例 1：
输入：nums = [7,52,2,4] 输出：596 解释：在执行任一步操作前，nums 为 [7,52,2,4] ，串联值为 0 。 - 在第一步操作中： 我们选中第一个元素 7 和最后一个元素 4 。 二者的串联是 74 ，将其加到串联值上，所以串联值等于 74 。 接着我们从 nums 中移除这两个元素，所以 nums 变为 [52,2] 。 - 在第二步操作中： 我们选中第一个元素 52 和最后一个元素 2 。 二者的串联是 522 ，将其加到串联值上，所以串联值等于 596 。 接着我们从 nums 中移除这两个元素，所以 nums 变为空。 由于串联值等于 596 ，所以答案就是 596 。
示例 2：
输入：nums = [5,14,13,8,12] 输出：673 解释：在执行任一步操作前，nums 为 [5,14,13,8,12] ，串联值为 0 。 - 在第一步操作中： 我们选中第一个元素 5 和最后一个元素 12 。 二者的串联是 512 ，将其加到串联值上，所以串联值等于 512 。 接着我们从 nums 中移除这两个元素，所以 nums 变为 [14,13,8] 。 - 在第二步操作中： 我们选中第一个元素 14 和最后一个元素 8 。 二者的串联是 148 ，将其加到串联值上，所以串联值等于 660 。 接着我们从 nums 中移除这两个元素，所以 nums 变为 [13] 。 - 在第三步操作中： nums 只有一个元素，所以我们选中 13 并将其加到串联值上，所以串联值等于 673 。 接着我们从 nums 中移除这个元素，所以 nums 变为空。 由于串联值等于 673 ，所以答案就是 673 。
提示：
1 <= nums.length <= 10001 <= nums[i] <= 104
解题思路
方法一：模拟
从数组两端开始，每次取出一个元素，将其与另一个元素拼接，然后将拼接后的结果加到答案中。重复这个过程，直到数组为空。
时间复杂度 ，空间复杂度 。其中 和 分别是数组的长度和数组中的最大值。
class Solution:
def findTheArrayConcVal(self, nums: List[int]) -> int:
ans = 0
i, j = 0, len(nums) - 1
while i < j:
ans += int(str(nums[i]) + str(nums[j]))
i, j = i + 1, j - 1
if i == j:
ans += nums[i]
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) since each element is processed exactly once with two-pointer scanning. Space complexity is O(1) additional space beyond input storage if string conversion is done in-place for concatenation. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Notice the need to process elements from both ends simultaneously for correct concatenation order.
- question_mark
Check for odd-length arrays to avoid double counting the middle element.
- question_mark
Simulate the concatenation process step by step rather than attempting a formulaic shortcut.
常见陷阱
外企场景- error
Forgetting to handle the single middle element in odd-length arrays, which leads to an incorrect total.
- error
Attempting numeric concatenation without string conversion, which fails for multi-digit numbers.
- error
Modifying the array incorrectly, which breaks the invariant of elements being counted exactly once.
进阶变体
外企场景- arrow_right_alt
Compute the concatenation value for arrays where numbers can have leading zeros, affecting string concatenation.
- arrow_right_alt
Return the intermediate total after each operation instead of only the final value.
- arrow_right_alt
Extend the problem to k-pair concatenation instead of just first and last elements, increasing pointer complexity.