Easy

题目描述

给你一个下标从 0 开始的整数数组 nums。

现定义两个数字的 连接 是由它们的数位相互连接形成的数字。

  • 例如，15 和 49 的连接是 1549。

nums 的 连接值 最初等于 0。执行下述操作直到 nums 变为空：

  • 如果 nums 中存在不止一个数字，选择 nums 中第一个元素和最后一个元素，将二者连接的结果加到 nums 的连接值上，然后从 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 <= 1000
  • 1 <= nums[i] <= 10^4

解题思路

这道题目要求我们模拟数组的连接过程。题目的关键在于理解操作规则：

  1. 双指针模拟：使用左右两个指针，分别指向数组的开头和结尾
  2. 连接操作：将两个数字连接起来，实际上就是将第一个数字转为字符串，再拼接第二个数字的字符串，最后转为整数
  3. 边界处理：当只剩一个元素时，直接加到结果中

算法步骤：

  1. 初始化左右指针 left = 0, right = n-1
  2. 当 left < right 时，连接 nums[left] 和 nums[right]，加到结果中，然后 left++, right--
  3. 当 left == right 时，说明只剩一个元素，直接加到结果中
  4. 返回最终结果

连接数字的方法：

  • 可以转为字符串拼接再转回整数
  • 也可以通过数学方法：first * pow(10, digits_of_second) + second

推荐使用字符串方法，代码更简洁易懂。

代码实现

class Solution {
public:
    long long findTheArrayConcVal(vector<int>& nums) {
        long long result = 0;
        int left = 0, right = nums.size() - 1;
        
        while (left < right) {
            string concat = to_string(nums[left]) + to_string(nums[right]);
            result += stoll(concat);
            left++;
            right--;
        }
        
        if (left == right) {
            result += nums[left];
        }
        
        return result;
    }
};

class Solution:
    def findTheArrayConcVal(self, nums: List[int]) -> int:
        result = 0
        left, right = 0, len(nums) - 1
        
        while left < right:
            concat = int(str(nums[left]) + str(nums[right]))
            result += concat
            left += 1
            right -= 1
        
        if left == right:
            result += nums[left]
        
        return result

public class Solution {
    public long FindTheArrayConcVal(int[] nums) {
        long result = 0;
        int left = 0, right = nums.Length - 1;
        
        while (left < right) {
            string concat = nums[left].ToString() + nums[right].ToString();
            result += long.Parse(concat);
            left++;
            right--;
        }
        
        if (left == right) {
            result += nums[left];
        }
        
        return result;
    }
}

var findTheArrayConcVal = function(nums) {
    let result = 0;
    let left = 0;
    let right = nums.length - 1;
    
    while (left <= right) {
        if (left === right) {
            result += nums[left];
        } else {
            result += parseInt(nums[left].toString() + nums[right].toString());
        }
        left++;
        right--;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n × k)，其中 n 是数组长度，k 是数字的平均位数（字符串转换的开销）
空间复杂度O(k)，字符串拼接时的临时空间开销