数组串联 图解题解
这道题到底在问什么
- 输入
- nums=[1,2,1]
- 输出
- [1,2,1,1,2,1]
- 输入
- nums=[1,3,2,1]
- 输出
- [1,3,2,1,1,3,2,1]
最优解：一步一步想明白
- 3记牢这一句:ans[i] 等于 nums[i mod n]。下面把 i 从 0 数到 9,每一步先读源数组的第 (i mod n) 个,再写进 ans 的第 i 格。
- 4开场:上面这条 ans 有 10 个格子,现在全是「·」表示还没填。右边侧栏是源数组 nums,一共 5 个数。接下来 i 从 0 走到 9,一格一格把 ans 填满。
- 5第 0 步,i mod n 还等于 i,就是 0。到侧栏读源数组第 0 个,值是 3。紫色格子是 ans 里马上要填的第 0 位。
- 6把 3 写进 ans 的第 0 格,它变绿点亮。继续往下一格走。
- 7第 1 步,i mod n 还等于 i,就是 1。到侧栏读源数组第 1 个,值是 8。紫色格子是 ans 里马上要填的第 1 位。
- 8把 8 写进 ans 的第 1 格,它变绿点亮。继续往下一格走。
- 9第 2 步,i mod n 还等于 i,就是 2。到侧栏读源数组第 2 个,值是 5。紫色格子是 ans 里马上要填的第 2 位。
- 10把 5 写进 ans 的第 2 格,它变绿点亮。继续往下一格走。
- 11第 3 步,i mod n 还等于 i,就是 3。到侧栏读源数组第 3 个,值是 6。紫色格子是 ans 里马上要填的第 3 位。
- 12把 6 写进 ans 的第 3 格,它变绿点亮。继续往下一格走。
- 13第 4 步,i mod n 还等于 i,就是 4。到侧栏读源数组第 4 个,值是 2。紫色格子是 ans 里马上要填的第 4 位。
- 14把 2 写进 ans 的第 4 格,它变绿点亮。到这里前半段填完了,ans 前 5 格正好是原数组。
- 15第 5 步,i 已经到 5,正好等于 n,来到后半段起点。i mod n 回绕成 0,回头读源数组第 0 个,值还是 3。后半段照抄前半段就从这里开始。
- 16把 3 写进 ans 的第 5 格,它变绿点亮。继续往下一格走。
- 17第 6 步,i 已经到 6,越过了前半段。i mod n 回绕成 1,又回头读源数组第 1 个,值还是 8。这正是后半段照抄前半段的地方。
- 18把 8 写进 ans 的第 6 格,它变绿点亮。继续往下一格走。
- 19第 7 步,i 已经到 7,越过了前半段。i mod n 回绕成 2,又回头读源数组第 2 个,值还是 5。这正是后半段照抄前半段的地方。
- 20把 5 写进 ans 的第 7 格,它变绿点亮。继续往下一格走。
- 21第 8 步,i 已经到 8,越过了前半段。i mod n 回绕成 3,又回头读源数组第 3 个,值还是 6。这正是后半段照抄前半段的地方。
- 22把 6 写进 ans 的第 8 格,它变绿点亮。继续往下一格走。
- 23第 9 步,i 已经到 9,越过了前半段。i mod n 回绕成 4,又回头读源数组第 4 个,值还是 2。这正是后半段照抄前半段的地方。
- 24把 2 写进 ans 的第 9 格,它变绿点亮。最后一格也填好了,整条 ans 全部点亮。
- 25拼完回看一眼:ans 的前 5 格和后 5 格一模一样,都是原数组 nums。这就是数组串联,答案是 [3,8,5,6,2,3,8,5,6,2]。整件事就是把 nums 抄两遍接起来。
⚠️ 容易写错的地方
✗ 错：只申请长度 n 的数组
✓ 对：答案长度必须是 2n
ans 要装下两份 nums,开小了后半段没地方放会越界
✗ 错：以为后半段要做某种变换或反转
✓ 对：后半段和前半段逐位相同
题目就是把 nums 原样再接一遍,不做任何加工
✗ 错：C++ 在循环条件里现算 nums.size() 当上界
✓ 对：先把原长度 n 存下来再循环
边 push_back 边读 size,长度一直在涨,循环永远到不了头
✗ 错：后半段下标写成 nums[i] 或漏取模
✓ 对：统一用 nums[i mod n]
i 到了 n 及以后,不取模会读到 nums 的越界位置,取模才能回绕到前半段
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
def getConcatenation(self, nums: List[int]) -> List[int]:
return nums + numsC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> getConcatenation(vector<int>& nums) {
for (int i = 0, n = nums.size(); i < n; ++i) {
nums.push_back(nums[i]);
}
return nums;
}
};Java
import java.util.*;
class Solution {
public int[] getConcatenation(int[] nums) {
int n = nums.length;
int[] ans = new int[n << 1];
for (int i = 0; i < n << 1; ++i) {
ans[i] = nums[i % n];
}
return ans;
}
}复杂度
时间
O(n)
ans 一共 2n 个位置,每个位置做一次读取加一次写入,都是常数操作,总量随 n 线性增长
空间
O(n)
需要一条长度 2n 的答案数组,规模就是 n 的量级;若把返回值本身不计入额外空间,则额外只用常数个变量,记 O(1)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 数组串联 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题的核心思路一句话怎么说?+
答案 ans 的第 i 位就是 nums[i mod n],等价于把 nums 首尾拼两遍。前一半照抄 nums,后一半靠取模回绕再抄一遍,长度是 2n。
有几种等价写法?+
至少三种:一是新开长度 2n 的数组按 i mod n 逐位填;二是像 Python 那样直接把两个 nums 列表相加拼接;三是像 C++ 那样先记住原长度 n,再在原数组尾部 push_back 补上 n 个副本。三者结果一致。
时间和空间复杂度分别是多少?+
时间 O(n),要给 2n 个位置各赋一次值;空间 O(n),用在长度 2n 的答案数组上,如果不把返回值计入额外空间,额外只用常数个变量,记 O(1)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 数组串联 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。