[{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"cpp","name":"","children":[{"text":"class Solution {\npublic:\n vector twoSum(vector& nums, int target) {\n // 注释里提到了冒泡查找（暴力解法）的时间复杂度，然后选择用hash（哈希表）优化\n map a; // 定义哈希表：key是数组中的数值，value是该数值对应的下标\n vectorb(2,-1); // 定义结果数组，初始值为-1（表示未找到），长度固定为2\n \n // 第一步：遍历数组，把所有数值和对应的下标存入哈希表\n for(int i = 0; i< nums.size();i++)\n a.insert(pair(nums[i],i)); // 存入：key=nums[i]，value=i\n \n // 第二步：再次遍历数组，查找是否存在“target - nums[i]”这个数\n for(int i = 0;i0：哈希表中存在“target - nums[i]”这个数\n // 2. a[target-nums[i]] != i：找到的数不能是当前数本身（避免同一个元素被重复使用）\n if(a.count(target-nums[i])>0&&a[target-nums[i]] != i)\n {\n b[0]= i; // 第一个数的下标\n b[1] = a[target -nums[i]]; // 第二个数的下标\n break; // 找到后直接退出循环\n }\n return b; // 返回结果数组\n }\n};"}],"slateId":"xFGMsPQ5KPq_U9GYVrzFx"}],"slateId":"5gfIKl6jdIUxH-IGESWFZ"},{"type":"Heading1","slateId":"XScjcAqQAlx_fYckudra_","children":[{"text":""}]},{"type":"Heading1","slateId":"mVYds1guKai5_UxKG_LU2","children":[{"text":"存在的问题"}]},{"type":"Heading2","slateId":"Gsd_2DkCQodXT84pix_G-","children":[{"text":"1.map 的 insert 方法不会覆盖已存在的键值对"}]},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"cpp","name":"","children":[{"text":"/*如果数组中有重复元素（比如 nums = [3,3]，target = 6）\n\ninsert 只会存入第一个 3 的下标，第二个 3 会插入失败，导致代码返回错误。\n\n改用 unordered_map 效率更高，且直接赋值覆盖\n*/\nunordered_map a; // unordered_map比map更快（哈希表 vs 红黑树）\n\n"}],"slateId":"bEKrKvDykj2o1U3GiU7Kz"}],"slateId":"-64NXfS5nthM3gN2zHEqn"},{"type":"Heading2","children":[{"text":""}],"slateId":"UVuzUI0JqdOF3V_h2_REP"},{"type":"Heading2","slateId":"eavrUiXhsJYcGuMBZSpWB","children":[{"text":"2.判断中使用[]，必须保证其一定存在，才不会「隐式插入」"}]},{"type":"Heading3","slateId":"LBuOGN9dDLshojZuoj5CV","children":[{"text":"2.1map[key] 的基本用法"}]},{"type":"Paragraph","slateId":"wbPC13fssUD7CcvaoumhL","children":[{"text":"map 重载了 [] 运算符，核心作用有两个："}]},{"type":"Heading6","slateId":"X6QkqJs_8K_mnzgEGI-O1","children":[{"text":"1.如果 key 已存在：返回该 key 对应的 value 的引用（可以直接读取或修改）；"}]},{"type":"Heading6","slateId":"URl-Sm8-2mBWSd2Bn65y-","children":[{"text":"2.如果 key 不存在：会自动插入一个以该 key 为键、value 为对应类型默认值（int 是 0，指针是 nullptr 等）的键值对，然后返回这个默认 value 的引用。"}]},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"cpp","name":"","children":[{"text":" for(int i = 0;i0：哈希表中存在“target - nums[i]”这个数\n // 2. a[target-nums[i]] != i：找到的数不能是当前数本身（避免同一个元素被重复使用）\n if(a.count(target-nums[i])>0&&a[target-nums[i]] != i)"}],"slateId":"vVf2GduG2w-PbUmezQVM_"}],"slateId":"7jRhE6T65t6N9iG6AORnx"},{"type":"Heading3","children":[{"text":"这里先用 a.count(target-nums[i])>0 判断 key 是否存在，再用 a[key] 取值，是安全的—— 因为 count 确保了 key 存在，不会触发隐式插入。"}],"slateId":"HfSZIV4vRosvnkQ17Equ0"},{"type":"Heading3","children":[{"text":""}],"slateId":"Y3R4q-aqUCeBVSpV9hf7D"},{"type":"Heading3","slateId":"DO3EbQ9vR1xJDXQuoGGIQ","children":[{"text":"2.2更安全的取值方式：map::find()"}]},{"type":"Paragraph","slateId":"X_iEi2iC2V8LmFeTG-Ltm","children":[{"text":"如果只想「读取」value 而不想触发隐式插入，推荐用 find() 方法："}]},{"type":"Paragraph","slateId":"oMzl0Fgr5jkHremzljXuZ","children":[{"text":"find(key) 返回一个迭代器：key 存在时指向该键值对，不存在时指向 map.end()；"}]},{"type":"Paragraph","slateId":"gCyblKQsvr28toTyJ7zq5","children":[{"text":"不会修改 map 的内容，更安全。"}]},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"cpp","name":"","children":[{"text":"// 用find替代[]，避免隐式插入\nauto it = a.find(target-nums[i]);\nif(it != a.end() && it->second != i) { // it->second 就是key对应的value\n b[0] = i;\n b[1] = it->second;\n break;\n}"}],"slateId":"LVKBNqR2NpOGjtEriPw29"}],"slateId":"x78URuGr8L_iLTRJN2ji4"},{"type":"Heading2","children":[{"text":""}],"slateId":"2S_dwpE1RSzB_OSrRl73f"},{"type":"Heading2","slateId":"9ST7N4x3EVkl6Tr6WlSEA","children":[{"text":"3.「先查后存」的逻辑从根源避免“匹配自身” 的问题"}]},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"cpp","name":"","children":[{"text":"#include \n#include \n\nusing namespace std;\n\nclass Solution {\npublic:\n vector twoSum(vector& nums, int target) {\n unordered_map num_map;\n for (int i = 0; i < nums.size(); ++i) {\n int complement = target - nums[i];\n // 找到互补数，直接返回结果\n if (num_map.count(complement)) {\n return {num_map[complement], i};\n }\n // 没找到就把当前数和下标存入哈希表\n num_map[nums[i]] = i;\n }\n // 题目保证有解，这里只是满足语法要求\n return {};\n }\n};"}],"slateId":"bAxHVctP9GQdFLTuqXdvG"}],"slateId":"5rHfcxcEhNq-FBhEDLyIr"},{"type":"Paragraph","children":[{"text":""}],"slateId":"cIrNiAoh6rb6k9l7rsFFh"}]