连接后等于目标字符串的字符串对 图解题解

要数的是哪种下标对，为什么不能当整数比

给一个数字字符串数组 nums 和一个数字字符串 target，问有多少有序对 (i,j) 满足 i≠j，且 nums[i] 接在前、nums[j] 接在后拼成的串正好等于 target。题面例子 nums=["777","7","77","77"]、target="7777"，答案 4。两点先钉死：一是有序对，(i,j) 和 (j,i) 算两种不同的对；二是按字符串原样拼，转成整数会丢前导 0、比错。

两层循环把每一对都拼一遍，账是多少

外层固定左串、内层轮流换右串，每凑一对就拼一次、和 target 比一次，只要 i≠j 就数进去。n 个串共 n×n 个有序对，扣掉 i=j 的 n 个都要试；每对都现拼新串逐字符比、约 O(m)。合起来 O(n²·m)。本题 n 和 target 长度都不超过 100，平方级跑得动，参考代码就是这种老实枚举。

target 只有一条接缝，能不能别逐对硬拼

拼出来要等于 target，那 nums[i] 必占 target 前半段、nums[j] 占后半段，接缝只能落在 target 内部某个位置。于是不必逐对硬拼：先拿一张哈希表，也就是记「串 → 出现几次」的账本，把每个串数清次数；再沿 target 挨个位置切一刀、切成前半串和后半串，命中这一刀的有序对数，等于两个串各自的出现次数相乘。

哈希配对怎么走一遍，相同串为什么要减一

target 有几个字符就有几减一个切分点，逐个切、逐个累加：前半串和后半串各查一次账本，出现次数相乘。要当心两半是同一个串时，同一个下标不能既当左又当右（否则 i=j），出现 k 次的串自己配自己只贡献 k×(k−1)、不是 k×k。

题面例子：账本是 "777" 一次、"7" 一次、"77" 两次。target="7777" 切成 "7"|"777" 得 1×1=1，切成 "77"|"77" 前后同串得 2×(2−1)=2，切成 "777"|"7" 得 1×1=1，加起来 1+2+1=4，和逐对枚举一样。

配成 "7777" 的到底是哪四对

把命中的对亲手数一遍。固定 "777" 当左串，只有下标 1 的 "7" 接上去拼成 "7777" 命中，其余长度都对不上。固定 "7" 当左串，配下标 0 的 "777" 拼成 "7777" 命中，和上一对顺序正好反过来。剩下两个 "77" 互相拼：下标 2 配 3、下标 3 配 2，各拼成 "7777" 一次，但谁都不能和自己拼（i≠j）。命中的有序对是 (0,1)、(1,0)、(2,3)、(3,2)，答案 4。

复杂度账，以及相同串一多答案涨得有多快

逐对枚举是 O(n²·m)：n² 个有序对、每对拼接加比较约 O(m)；空间 O(m)，临时拼出的新串用完即弃、不随对数膨胀。改哈希计数只枚举 m−1 个切分点、每刀查两次账本，比逐对少扫全部下标对。

边界校准：数组只有 2 个串最多顺拼中一次记 1；两个完全相同的串正反各中一次记 2。相同串越多涨得越猛，同一个串出现 3 次且自拼等于 target，有序对是 3×2=6，先挑两个不同下标、再考虑左右顺序。

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 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)
        )

C++

#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:
    int numOfPairs(vector<string>& nums, string target) {
        int n = nums.size();
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i != j && nums[i] + nums[j] == target) ++ans;
            }
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int numOfPairs(String[] nums, String target) {
        int n = nums.length;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i != j && target.equals(nums[i] + nums[j])) {
                    ++ans;
                }
            }
        }
        return ans;
    }
}