企业官网建设流程全解析

LeetCode 760 Find Anagram Mappings 全解：暴力、哈希表与位运算三种解法（含多语言实现）

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

导读

本篇基于 find-anagram-mappings.md 深入讲解 LeetCode 760「寻找变位词映射」：给定两个互为 anagram 的数组nums1与nums2，为nums1中每个元素找到其在nums2中的下标。文章完整覆盖三种解法——暴力双重循环（O(N²)）、哈希表预处理（O(N)）以及位运算 + 排序（O(N log N)），并提供 Python、Java、C++、JavaScript、Go、Kotlin、Swift、Rust 共 8 种语言的完整实现。读完你将掌握「值 → 下标」映射建模、位打包编码技巧及其适用边界，并能据此迁移解决同类数组映射类问题。

前置知识

在尝试该题之前，建议先熟悉以下基础：

• 哈希表（Hash Maps）：用于存储「值 → 下标」映射，实现 O(1) 查询，是本题最优解的核心数据结构；
• 数组遍历（Array Traversal）：在两个数组之间构建映射关系的基本迭代能力；
• 位运算（Bit Manipulation，可选）：进阶解法利用位左移把下标直接编码进元素值中，从而省去哈希表的额外空间。

本题与仓库中另外两篇 anagram 主题文章同属「哈希 + 数组」体系：变位词分组见 anagram-groups.md（用排序串或字符计数做 key），判断两串是否为变位词见 is-anagram.md。三题的核心建模思路一脉相承，可对照学习。

问题本质：把「值」翻译成「下标」

题目要求对nums1的每个元素，找出它在nums2中的任意一个出现位置，输出与nums1等长的下标数组。由于两个数组互为 anagram（元素多重集相同），nums1中的每个值必然能在nums2中找到，因此无需处理「查不到」的情况——这一点是三种解法的共同前提。

从仓库源码结构看，本仓库为每个 LeetCode 题目在 python、java、cpp、javascript、go、kotlin、swift、rust 等目录下各维护一份独立解法文件（如 python/0001-two-sum.py 对应 Two Sum），而 articles 目录则存放配套讲解。下面按复杂度从低到高给出三种解法。

1. 暴力解法：双重循环逐个匹配

思路（Intuition）

问题要求的是：对于nums1中的每个元素，在nums2中找到该值出现的下标。最朴素的做法是对nums1的每个元素，遍历nums2的全部位置：一旦找到相等元素就记录下标并停止。由于穷举了所有可能性，正确性有保证。

算法步骤

1. 创建与nums1等长的结果数组mappings；
2. 对nums1的每个下标i：
   • 用下标j遍历nums2；
   • 当nums1[i] == nums2[j]时，将j存入mappings[i]并break；
3. 返回mappings。

多语言实现

class Solution: def anagramMappings(self, nums1: List[int], nums2: List[int]) -> List[int]: # List to store the anagram mappings. mappings = [0] * len(nums1) for i in range(len(nums1)): for j in range(len(nums2)): # Store the corresponding index of number in the second list. if nums1[i] == nums2[j]: mappings[i] = j break return mappings

class Solution { public int[] anagramMappings(int[] nums1, int[] nums2) { // List to store the anagram mappings. int[] mappings = new int[nums1.length]; for (int i = 0; i < nums1.length; i++) { for (int j = 0; j < nums2.length; j++) { // Store the corresponding index of number in the second list. if (nums1[i] == nums2[j]) { mappings[i] = j; break; } } } return mappings; } }

class Solution { public: vector<int> anagramMappings(vector<int>& nums1, vector<int>& nums2) { // List to store the anagram mappings. vector<int> mappings; for (int num : nums1) { for (int i = 0; i < nums2.size(); i++) { // Store the corresponding index of number in the second list. if (num == nums2[i]) { mappings.push_back(i); break; } } } return mappings; } };

class Solution { /** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number[]} */ anagramMappings(nums1, nums2) { // Array to store the anagram mappings. const mappings = new Array(nums1.length); for (let i = 0; i < nums1.length; i++) { for (let j = 0; j < nums2.length; j++) { // Store the corresponding index of number in the second array. if (nums1[i] === nums2[j]) { mappings[i] = j; break; } } } return mappings; } }

func anagramMappings(nums1 []int, nums2 []int) []int { // Slice to store the anagram mappings. mappings := make([]int, len(nums1)) for i := 0; i < len(nums1); i++ { for j := 0; j < len(nums2); j++ { // Store the corresponding index of number in the second slice. if nums1[i] == nums2[j] { mappings[i] = j break } } } return mappings }

class Solution { fun anagramMappings(nums1: IntArray, nums2: IntArray): IntArray { // Array to store the anagram mappings. val mappings = IntArray(nums1.size) for (i in nums1.indices) { for (j in nums2.indices) { // Store the corresponding index of number in the second array. if (nums1[i] == nums2[j]) { mappings[i] = j break } } } return mappings } }

class Solution { func anagramMappings(_ nums1: [Int], _ nums2: [Int]) -> [Int] { // Array to store the anagram mappings. var mappings = Int for i in 0..<nums1.count { for j in 0..<nums2.count { // Store the corresponding index of number in the second array. if nums1[i] == nums2[j] { mappings[i] = j break } } } return mappings } }

impl Solution { pub fn anagram_mappings(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> { let mut mappings = vec![0i32; nums1.len()]; for i in 0..nums1.len() { for j in 0..nums2.len() { if nums1[i] == nums2[j] { mappings[i] = j as i32; break; } } } mappings } }

复杂度分析

• 时间复杂度：O(N²)—— 最坏情况下nums1每个元素都要扫描完整的nums2；
• 空间复杂度：O(1)—— 除结果数组外只使用常数级额外空间。

其中 N 为数组nums1和nums2的元素个数。

暴力法的性能瓶颈在于「重复扫描」：nums2被反复遍历 N 次。下一节用哈希表把查询降到常数时间。

2. 哈希表解法：一次预处理，O(1) 查询

思路（Intuition）

与其反复扫描nums2，不如先把它预处理成一张「值 → 下标」的哈希表，此后对nums1的任意元素都能在常数时间内取到对应下标。由于两个数组互为 anagram，nums1中的每个元素都保证存在于nums2中，查找不会落空。

算法步骤

1. 构建哈希表valueToPos：遍历nums2，以值为 key、下标为 value；
2. 创建结果数组mappings；
3. 遍历nums1的每个元素，从哈希表中查出其下标存入mappings；
4. 返回mappings。

多语言实现

class Solution: def anagramMappings(self, nums1: List[int], nums2: List[int]) -> List[int]: # Store the index corresponding to the value in the second list. valueToPos = {} for i in range(len(nums2)): valueToPos[nums2[i]] = i # List to store the anagram mappings. mappings = [0] * len(nums1) for i in range(len(nums1)): mappings[i] = valueToPos[nums1[i]] return mappings

class Solution { public int[] anagramMappings(int[] nums1, int[] nums2) { // Store the index corresponding to the value in the second list. HashMap<Integer,Integer> valueToPos = new HashMap<>(); for (int i = 0; i < nums2.length; i++) { valueToPos.put(nums2[i], i); } // List to store the anagram mappings. int[] mappings = new int[nums1.length]; for (int i = 0; i < nums1.length; i++) { mappings[i] = valueToPos.get(nums1[i]); } return mappings; } }

class Solution { public: vector<int> anagramMappings(vector<int>& nums1, vector<int>& nums2) { // Store the index corresponding to the value in the second list. unordered_map<int, int> valueToPos; for (int i = 0; i < nums2.size(); i++) { valueToPos[nums2[i]] = i; } // List to store the anagram mappings. vector<int> mappings; for (int num : nums1) { mappings.push_back(valueToPos[num]); } return mappings; } };

class Solution { /** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number[]} */ anagramMappings(nums1, nums2) { // Store the index corresponding to the value in the second list. const valueToPos = new Map(); for (let i = 0; i < nums2.length; i++) { valueToPos.set(nums2[i], i); } // List to store the anagram mappings. const mappings = new Array(nums1.length); for (let i = 0; i < nums1.length; i++) { mappings[i] = valueToPos.get(nums1[i]); } return mappings; } }

func anagramMappings(nums1 []int, nums2 []int) []int { // Store the index corresponding to the value in the second slice. valueToPos := make(map[int]int) for i := 0; i < len(nums2); i++ { valueToPos[nums2[i]] = i } // Slice to store the anagram mappings. mappings := make([]int, len(nums1)) for i := 0; i < len(nums1); i++ { mappings[i] = valueToPos[nums1[i]] } return mappings }

class Solution { fun anagramMappings(nums1: IntArray, nums2: IntArray): IntArray { // Store the index corresponding to the value in the second array. val valueToPos = HashMap<Int, Int>() for (i in nums2.indices) { valueToPos[nums2[i]] = i } // Array to store the anagram mappings. val mappings = IntArray(nums1.size) for (i in nums1.indices) { mappings[i] = valueToPos[nums1[i]]!! } return mappings } }

class Solution { func anagramMappings(_ nums1: [Int], _ nums2: [Int]) -> [Int] { // Store the index corresponding to the value in the second array. var valueToPos = [Int: Int]() for i in 0..<nums2.count { valueToPos[nums2[i]] = i } // Array to store the anagram mappings. var mappings = Int for i in 0..<nums1.count { mappings[i] = valueToPos[nums1[i]]! } return mappings } }

impl Solution { pub fn anagram_mappings(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> { let mut value_to_pos = HashMap::new(); for (i, &num) in nums2.iter().enumerate() { value_to_pos.insert(num, i as i32); } let mut mappings = vec![0i32; nums1.len()]; for (i, &num) in nums1.iter().enumerate() { mappings[i] = value_to_pos[&num]; } mappings } }

复杂度分析

• 时间复杂度：O(N)—— 构建哈希表一次 O(N)，查询 N 次每次 O(1)；
• 空间复杂度：O(N)—— 哈希表存储 N 个「值 → 下标」键值对。

其中 N 为数组nums1和nums2的元素个数。

这是面试中最推荐给出的解法：思路直观（与 two-integer-sum.md 中「值 → 下标」哈希表的建模方式同源），且达到线性复杂度下界。唯一代价是需要 O(N) 的额外空间，下一节介绍如何用位运算把这部分空间也省掉。

3. 位运算 + 排序解法：把下标编码进元素里

思路（Intuition）

哈希表解法的额外空间来自那张valueToPos表。能否把「原始下标」直接保存在元素自身、从而省去哈希表？可以——利用位运算：把每个值左移若干位，再叠加自己的下标，这样一个整数里同时保留了「原值」和「原下标」两份信息。排序两个数组后，原值相同的元素必然对齐到相同位置，此时只需用掩码提取下标并配对即可。

算法步骤

1. 对每个下标i，编码两个数组：nums[i] = (nums[i] << 7) + i。左移位数（此处取 7 位）必须足够容纳最大下标；
2. 分别排序nums1与nums2，原值相等的元素此时出现在相同位置；
3. 创建结果数组mappings；
4. 对每个位置i，用掩码提取原始下标：mappings[nums1[i] & mask] = nums2[i] & mask；
5. 返回mappings。

为什么左移 7 位？

numToGetLastBits = (1 << 7) - 1 = 127，即低 7 位全部为 1 的掩码。左移 7 位后，低 7 位被腾空用于存放下标，因此下标取值范围为 0～127，即最多支持长度 128 的数组（LeetCode 该题约束下 N ≤ 100 时可安全使用；若数组更大，需要相应增大bitsToShift）。提取下标时用& 127只取低 7 位，原值信息则完整保留在高位，排序时天然按「原值 → 下标」的字典序排列，保证相同原值聚在一起且顺序一致。

多语言实现

class Solution: def anagramMappings(self, nums1: List[int], nums2: List[int]) -> List[int]: bitsToShift = 7 numToGetLastBits = (1 << bitsToShift) - 1 # Store the index within the integer itself. for i in range(len(nums1)): nums1[i] = (nums1[i] << bitsToShift) + i nums2[i] = (nums2[i] << bitsToShift) + i # Sort both lists so that the original integers end up at the same index. nums1.sort() nums2.sort() # List to store the anagram mappings. mappings = [0] * len(nums1) for i in range(len(nums1)): # Store the index in the second list corresponding to the integer index in the first list. mappings[nums1[i] & numToGetLastBits] = (nums2[i] & numToGetLastBits) return mappings

class Solution { final int bitsToShift = 7; final int numToGetLastBits = (1 << bitsToShift) - 1; public int[] anagramMappings(int[] nums1, int[] nums2) { // Store the index within the integer itself. for (int i = 0; i < nums1.length; i++) { nums1[i] = (nums1[i] << bitsToShift) + i; nums2[i] = (nums2[i] << bitsToShift) + i; } // Sort both lists so that the original integers end up at the same index. Arrays.sort(nums1); Arrays.sort(nums2); // List to store the anagram mappings. int[] mappings = new int[nums1.length]; for (int i = 0; i < nums1.length; i++) { // Store the index in the second list corresponding to the integer index in the first list. mappings[nums1[i] & numToGetLastBits] = (nums2[i] & numToGetLastBits); } return mappings; } }

class Solution { public: const int bitsToShift = 7; const int numToGetLastBits = (1 << bitsToShift) - 1; vector<int> anagramMappings(vector<int>& nums1, vector<int>& nums2) { // Store the index within the integer itself. for (int i = 0; i < nums1.size(); i++) { nums1[i] = (nums1[i] << bitsToShift) + i; nums2[i] = (nums2[i] << bitsToShift) + i; } // Sort both lists so that the original integers end up at the same index. sort(nums1.begin(), nums1.end()); sort(nums2.begin(), nums2.end()); // List to store the anagram mappings. vector<int> mappings(nums1.size()); for (int i = 0; i < nums1.size(); i++) { // Store the index in the second list corresponding to the integer index in the first list. mappings[nums1[i] & numToGetLastBits] = (nums2[i] & numToGetLastBits); } return mappings; } };

class Solution { /** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number[]} */ anagramMappings(nums1, nums2) { const bitsToShift = 7; const numToGetLastBits = (1 << bitsToShift) - 1; // Store the index within the integer itself. for (let i = 0; i < nums1.length; i++) { nums1[i] = (nums1[i] << bitsToShift) + i; nums2[i] = (nums2[i] << bitsToShift) + i; } // Sort both arrays so that the original integers end up at the same index. nums1.sort((a, b) => a - b); nums2.sort((a, b) => a - b); // Array to store the anagram mappings. const mappings = new Array(nums1.length); for (let i = 0; i < nums1.length; i++) { // Store the index in the second array corresponding to the integer index in the first array. mappings[nums1[i] & numToGetLastBits] = (nums2[i] & numToGetLastBits); } return mappings; } }

func anagramMappings(nums1 []int, nums2 []int) []int { bitsToShift := 7 numToGetLastBits := (1 << bitsToShift) - 1 // Store the index within the integer itself. for i := 0; i < len(nums1); i++ { nums1[i] = (nums1[i] << bitsToShift) + i nums2[i] = (nums2[i] << bitsToShift) + i } // Sort both slices so that the original integers end up at the same index. sort.Ints(nums1) sort.Ints(nums2) // Slice to store the anagram mappings. mappings := make([]int, len(nums1)) for i := 0; i < len(nums1); i++ { // Store the index in the second slice corresponding to the integer index in the first slice. mappings[nums1[i] & numToGetLastBits] = nums2[i] & numToGetLastBits } return mappings }

class Solution { fun anagramMappings(nums1: IntArray, nums2: IntArray): IntArray { val bitsToShift = 7 val numToGetLastBits = (1 shl bitsToShift) - 1 // Store the index within the integer itself. for (i in nums1.indices) { nums1[i] = (nums1[i] shl bitsToShift) + i nums2[i] = (nums2[i] shl bitsToShift) + i } // Sort both arrays so that the original integers end up at the same index. nums1.sort() nums2.sort() // Array to store the anagram mappings. val mappings = IntArray(nums1.size) for (i in nums1.indices) { // Store the index in the second array corresponding to the integer index in the first array. mappings[nums1[i] and numToGetLastBits] = nums2[i] and numToGetLastBits } return mappings } }

class Solution { func anagramMappings(_ nums1: [Int], _ nums2: [Int]) -> [Int] { var nums1 = nums1 var nums2 = nums2 let bitsToShift = 7 let numToGetLastBits = (1 << bitsToShift) - 1 // Store the index within the integer itself. for i in 0..<nums1.count { nums1[i] = (nums1[i] << bitsToShift) + i nums2[i] = (nums2[i] << bitsToShift) + i } // Sort both arrays so that the original integers end up at the same index. nums1.sort() nums2.sort() // Array to store the anagram mappings. var mappings = Int for i in 0..<nums1.count { // Store the index in the second array corresponding to the integer index in the first array. mappings[nums1[i] & numToGetLastBits] = nums2[i] & numToGetLastBits } return mappings } }

impl Solution { pub fn anagram_mappings(mut nums1: Vec<i32>, mut nums2: Vec<i32>) -> Vec<i32> { let bits_to_shift = 7; let num_to_get_last_bits = (1 << bits_to_shift) - 1; for i in 0..nums1.len() { nums1[i] = (nums1[i] << bits_to_shift) + i as i32; nums2[i] = (nums2[i] << bits_to_shift) + i as i32; } nums1.sort(); nums2.sort(); let mut mappings = vec![0i32; nums1.len()]; for i in 0..nums1.len() { mappings[(nums1[i] & num_to_get_last_bits) as usize] = nums2[i] & num_to_get_last_bits; } mappings } }

复杂度分析

• 时间复杂度：O(N log N)—— 两次排序占主导，编码与配对均为 O(N)；
• 空间复杂度：O(log N)—— 排序所需的递归栈空间，无需额外哈希表。

其中 N 为数组nums1和nums2的元素个数。

该解法的适用前提与限制

• 编码是原地修改输入数组（如 Swift 版本需先拷贝为var），排序也会打乱原始顺序，若后续还需原数组则需额外拷贝；
• 左移位数必须按数组长度上限选取：7 位只支持下标 0～127。若 N 更大，需要增大bitsToShift并同步更新掩码；
• 该解法牺牲了时间（O(N log N)）换取空间（O(1) 级），属于「空间换时间」的反向权衡，理解其位打包思想的价值大于实际工程用途。

常见陷阱（Common Pitfalls）

陷阱一：重复值的下标被覆盖

使用哈希表时，每个值只存一个下标，重复出现的值会全部映射到同一个下标。如果题目要求重复值各自映射到不同下标，就不能用「单值 → 单下标」的表，而应改为存储下标列表（如Map<Integer, List<Integer>>），或使用下标栈并逐个弹出（pop），保证每个下标只被使用一次。本题标准版本对重复值不做区分、任意合法下标均可，但面试时应主动和面试官确认重复值的语义。

陷阱二：位运算的 off-by-one 与下标碰撞

用位运算编码下标时，如果左移位数选得太少，较大的下标会「溢出」到高位，导致不同元素编码后碰撞、排序后无法正确对齐。选取移位位数时，必须保证2^bitsToShift > maxIndex，即 bits 足够容纳可能出现的最大下标（例如 N=100 时需要至少 7 位，因为 2^7=128 > 100）。

三种解法速览与选型建议

扩展阅读

• 同类「值 → 下标」哈希建模：two-integer-sum.md、two-integer-sum-ii.md
• 变位词家族其他题目：anagram-groups.md、is-anagram.md、find-all-anagrams-in-a-string.md
• 哈希表设计的工程实践：design-hashmap.md、design-hashset.md

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode