Medium

题目描述

给你一个数字字符串数组 nums 和一个数字字符串 target ，请你返回 nums[i] + nums[j] （两字符串连接）结果等于 target 的下标 (i, j) （需满足 i != j）的数目。

示例 1：

输入：nums = ["777","7","77","77"], target = "7777"
输出：4
解释：有效配对为：
- (0, 1): "777" + "7"
- (1, 0): "7" + "777"
- (2, 3): "77" + "77"
- (3, 2): "77" + "77"

示例 2：

输入：nums = ["123","4","12","34"], target = "1234"
输出：2
解释：有效配对为：
- (0, 1): "123" + "4"
- (2, 3): "12" + "34"

示例 3：

输入：nums = ["1","1","1"], target = "11"
输出：6
解释：有效配对为：
- (0, 1): "1" + "1"
- (1, 0): "1" + "1"
- (0, 2): "1" + "1"
- (2, 0): "1" + "1"
- (1, 2): "1" + "1"
- (2, 1): "1" + "1"

提示：

  • 2 <= nums.length <= 100
  • 1 <= nums[i].length <= 100
  • 2 <= target.length <= 100
  • nums[i] 和 target 只包含数字
  • nums[i] 和 target 不含前导零

解题思路

解题思路

这道题要求找到所有满足 nums[i] + nums[j] = target 的下标对 (i, j)，其中 i != j。

方法一：暴力枚举（推荐）

最直观的思路是枚举所有可能的下标对，检查字符串连接后是否等于目标字符串。由于数组长度最多100，O(n²) 的时间复杂度完全可以接受。

具体步骤：

  1. 使用双重循环枚举所有 i != j 的下标对
  2. 将 nums[i] 和 nums[j] 连接，检查是否等于 target
  3. 统计满足条件的配对数量

方法二：哈希表优化

可以使用哈希表来优化，对于每个字符串，找到能与它组成目标字符串的前缀或后缀：

  1. 遍历 target 的所有可能分割点
  2. 统计数组中每个字符串的出现次数
  3. 对每个分割，计算左部分和右部分在数组中的出现次数
  4. 需要特别处理左右部分相同的情况

但考虑到数据规模较小，暴力解法更简洁且性能足够。

代码实现

class Solution {
public:
    int numOfPairs(vector<string>& nums, string target) {
        int count = 0;
        int n = nums.size();
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j && nums[i] + nums[j] == target) {
                    count++;
                }
            }
        }
        
        return count;
    }
};

class Solution:
    def numOfPairs(self, nums: List[str], target: str) -> int:
        count = 0
        n = len(nums)
        
        for i in range(n):
            for j in range(n):
                if i != j and nums[i] + nums[j] == target:
                    count += 1
        
        return count

public class Solution {
    public int NumOfPairs(string[] nums, string target) {
        int count = 0;
        int n = nums.Length;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j && nums[i] + nums[j] == target) {
                    count++;
                }
            }
        }
        
        return count;
    }
}

/**
 * @param {string[]} nums
 * @param {string} target
 * @return {number}
 */
var numOfPairs = function(nums, target) {
    let count = 0;
    
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < nums.length; j++) {
            if (i !== j && nums[i] + nums[j] === target) {
                count++;
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n² × L)，其中 n 是数组长度，L 是字符串平均长度，字符串连接操作需要 O(L) 时间
空间复杂度O(L)，字符串连接时需要额外的空间存储结果

相关题目