题目描述
思路解析动画文字版
记牢这一句:外层固定左串,内层轮流拿右串接上去拼一次、和 target 比一次,i ≠ j 就好。下面每一帧都在套这句。
总览 · 数组 + 目标串：先看清画面。上面是 nums = ["777","7","77","77"],一共 4 个数字串。我们的目标串 target = "7777"。答案 ans 从 0 起步。接下来紫色的 i 指针会固定一个左串,再让每个右串轮流接上去拼一次、和 target 比一次:拼中了那格标绿,拼不中标红,i 和 j 撞在一起就跳过。先从左串 nums[0] 开始。
第一轮 · 固定左串 nums[0] = "777"：第 0 轮开始。紫色 i 指针停在下标 0,把 nums[0] = "777" 定为这一轮的左串。接下来让右串 j 从下标 0 一路走到 3,每停一格就把那格的串接到 "777" 后面,拼出来和 target 对一对。
第一轮 · j = 0 撞上 i,跳过：右串 j 走到下标 0,正好和左串的 i 撞在同一格。题目要求 i ≠ j,同一个位置的字符串不能和它自己拼,所以这一格直接跳过,不拼也不比。j 继续往后走。
第一轮 · j = 1 命中,ans → 1：右串 j 停在下标 1,把 "7" 接到左串 "777" 后面,拼成 "7777"。它和 target = "7777" 一模一样,命中!这一对 (0, 1) 有效,那格标绿,ans 加到 1。
第一轮 · j = 2 落空：右串 j 停在下标 2,把 "77" 接到 "777" 后面,拼成 "77777"。它和 target = "7777" 不一样(长度都对不上),不算数,那格标红,ans 不变,还是 1。
第一轮 · j = 3 落空：右串 j 停在下标 3,把 "77" 接到 "777" 后面,拼成 "77777"。它和 target = "7777" 不一样(长度都对不上),不算数,那格标红,ans 不变,还是 1。
第二轮 · 固定左串 nums[1] = "7"：第 1 轮开始。紫色 i 指针停在下标 1,把 nums[1] = "7" 定为这一轮的左串。接下来让右串 j 从下标 0 一路走到 3,每停一格就把那格的串接到 "7" 后面,拼出来和 target 对一对。
第二轮 · j = 0 命中,ans → 2：右串 j 停在下标 0,把 "777" 接到左串 "7" 后面,拼成 "7777"。它和 target = "7777" 一模一样,命中!这一对 (1, 0) 有效,那格标绿,ans 加到 2。
第二轮 · j = 1 撞上 i,跳过：右串 j 走到下标 1,正好和左串的 i 撞在同一格。题目要求 i ≠ j,同一个位置的字符串不能和它自己拼,所以这一格直接跳过,不拼也不比。j 继续往后走。
第二轮 · j = 2 落空：右串 j 停在下标 2,把 "77" 接到 "7" 后面,拼成 "777"。它和 target = "7777" 不一样(长度都对不上),不算数,那格标红,ans 不变,还是 2。
第二轮 · j = 3 落空：右串 j 停在下标 3,把 "77" 接到 "7" 后面,拼成 "777"。它和 target = "7777" 不一样(长度都对不上),不算数,那格标红,ans 不变,还是 2。
第三轮 · 固定左串 nums[2] = "77"：第 2 轮开始。紫色 i 指针停在下标 2,把 nums[2] = "77" 定为这一轮的左串。接下来让右串 j 从下标 0 一路走到 3,每停一格就把那格的串接到 "77" 后面,拼出来和 target 对一对。
第三轮 · j = 0 落空：右串 j 停在下标 0,把 "777" 接到 "77" 后面,拼成 "77777"。它和 target = "7777" 不一样(长度都对不上),不算数,那格标红,ans 不变,还是 2。
第三轮 · j = 1 落空：右串 j 停在下标 1,把 "7" 接到 "77" 后面,拼成 "777"。它和 target = "7777" 不一样(长度都对不上),不算数,那格标红,ans 不变,还是 2。
第三轮 · j = 2 撞上 i,跳过：右串 j 走到下标 2,正好和左串的 i 撞在同一格。题目要求 i ≠ j,同一个位置的字符串不能和它自己拼,所以这一格直接跳过,不拼也不比。j 继续往后走。
第三轮 · j = 3 命中,ans → 3：右串 j 停在下标 3,把 "77" 接到左串 "77" 后面,拼成 "7777"。它和 target = "7777" 一模一样,命中!这一对 (2, 3) 有效,那格标绿,ans 加到 3。
第四轮 · 固定左串 nums[3] = "77"：第 3 轮开始。紫色 i 指针停在下标 3,把 nums[3] = "77" 定为这一轮的左串。接下来让右串 j 从下标 0 一路走到 3,每停一格就把那格的串接到 "77" 后面,拼出来和 target 对一对。
第四轮 · j = 0 落空：右串 j 停在下标 0,把 "777" 接到 "77" 后面,拼成 "77777"。它和 target = "7777" 不一样(长度都对不上),不算数,那格标红,ans 不变,还是 3。
第四轮 · j = 1 落空：右串 j 停在下标 1,把 "7" 接到 "77" 后面,拼成 "777"。它和 target = "7777" 不一样(长度都对不上),不算数,那格标红,ans 不变,还是 3。
第四轮 · j = 2 命中,ans → 4：右串 j 停在下标 2,把 "77" 接到左串 "77" 后面,拼成 "7777"。它和 target = "7777" 一模一样,命中!这一对 (3, 2) 有效,那格标绿,ans 加到 4。
第四轮 · j = 3 撞上 i,跳过：右串 j 走到下标 3,正好和左串的 i 撞在同一格。题目要求 i ≠ j,同一个位置的字符串不能和它自己拼,所以这一格直接跳过,不拼也不比。j 继续往后走。
完成 · 字符串对 = 4：四轮枚举全部走完。命中的有序对是 (0, 1)、(1, 0)、(2, 3)、(3, 2):"777"+"7" 和反过来 "7"+"777" 各一对,两个 "77" 正反接成 "77"+"77" 又各一对,合起来正好 4 对,和题面答案对上了。整道题的窍门就一句:枚举所有 i ≠ j 的有序对,拼一次比一次,数出等于 target 的有几对。
边界:n = 2 时只顺拼中记 1;两个相同串正反各中记 2;三个相同串有序对 3×2 = 6。相同串越多,有序对增长越快。
面试重点:暴力枚举有序对逐一拼接比对;进阶可用哈希统计次数再枚举 target 切分点求前后缀次数乘积;Java 比字符串必须用 equals。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def numOfPairs(self, nums: List[str], target: str) -> int: n = len(nums) return sum( i != j and nums[i] + nums[j] == target for i in range(n) for j in range(n) )复杂度
- 时间：O(n² · m)，n 是数组长度,m 是 target 的长度。外层 i、内层 j 各扫 n 次,一共 n 乘 n 个有序对;每对都要做一次字符串拼接和一次比较,拼接与比较的代价随串长走,约为 O(m)。所以总时间是 O(n² · m)。本题 n 和 m 都不超过 100,平方级完全跑得动
- 空间：O(m)，按峰值算。除计数变量外,每次拼接会临时生成一个长度约为 m 的新字符串来和 target 比,用完即弃,峰值就是这一个临时串的长度 O(m)。不额外开随 n 增长的表,所以空间只和串长有关,不随下标对数量膨胀
易错点
面试追问把动画讲成自己的话
追问这题最直接的思路是什么?
追问有没有更快的做法?
追问三种语言实现上要注意什么?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
给植物浇水
LeetCode 2079 · 中等 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题