【算法打卡day20（2026-03-12 周四）算法/技巧：哈希表，双指针，字符串交换处理】5个题

- 第 187 篇 -
Date: 2026 - 03- 13 | 周五
Author: 郑龙浩（仟墨）
算法/技巧：哈希表，双指针，字符串交换处理

2026-03-13-算法打卡day21

按照「代码随想录」题单刷题
算法/技巧：哈希表，双指针，字符串交换处理
前三个题都是「代码随想录」中「哈希表」最后的三个题，但是 2 和 3 都是双指针，其实不是哈希表的题
然后后面的几个题都是「代码随想录」中「字符串」的题了

今天的课特别多，所以晚上才开始刷题，刷的题特少

1-力扣383-赎金信

题目难度：简单
算法/技巧：哈希表

【题目】

给你两个字符串：ransomNote和magazine，判断ransomNote能不能由magazine里面的字符构成。

如果可以，返回true；否则返回false。

magazine中的每个字符只能在ransomNote中使用一次。

示例 1：

**输入：**ransomNote = “a”, magazine = “b”
**输出：**false

示例 2：

**输入：**ransomNote = “aa”, magazine = “ab”
**输出：**false

示例 3：

**输入：**ransomNote = “aa”, magazine = “aab”
**输出：**true

提示：

• 1 <= ransomNote.length, magazine.length <= 105
• ransomNote和magazine由小写英文字母组成

【思路】

没什么技巧，就是将第二个字符串用map存储起来（charCnt)，key是magazin中出现的字符，value是该字符出现的次数

然后循环便利ransomNote

• ch如果在magazine中没有，那么直接return false
• ch如果在magazine中出现过，但是字符数量为0，就说明此前使用过1次或多次该字符，此时字符不够用了，也要return false
  循环的时候，每使用一次某字符，某字符都要将次数–

【代码】

/* 1-力扣383-赎金信 Author：郑龙浩 Date：2026-03-13 哈希表 用时：21min （charCnt[magazine[i]]++;不小心写成了=i,找了好久的错，没想到是这里误写了） */#include"bits/stdc++.h"usingnamespacestd;classSolution{public:boolcanConstruct(string ransomNote,string magazine){unordered_map<char,int>charCnt;// 存储magazine的字符和该字符出现过的次数for(inti=0;i<magazine.size();i++)charCnt[magazine[i]]++;for(charch:ransomNote){autoans=charCnt.find(ch);// cout << ans->first << ' ' << ans->second << '\n'; // 检验if(ans==charCnt.end()||ans->second==0){// 如果 本该字符在magazine中就不存在 || 在magazin找到对应下标 且 字符为0 （之前使用过magazine中的该字符，且该字符已经用完了）returnfalse;}ans->second-=1;// 使用了一次magazine中的该字符，就要减去一次使用次数}// 如果一直没有返回false，就说明组成成功了returntrue;}};intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);Solution sol;cout<<sol.canConstruct("aa","aab");return0;}

2-力扣15-三数之和

题目难度：中等
算法/技巧：双指针

【题目】

给你一个整数数组nums，判断是否存在三元组[nums[i], nums[j], nums[k]]满足i != j、i != k且j != k，同时还满足nums[i] + nums[j] + nums[k] == 0。请你返回所有和为0且不重复的三元组。

**注意：**答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0
不同的三元组是[-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：

• 3 <= nums.length <= 3000
• -105 <= nums[i] <= 105

【思路】

刚开始我是想的用「哈希表」，后来发现，哈希表很复杂， 对我来说不太好实现

看了题解后，才知道应该使用「双指针」，且该双指针有点像二分查找

大概思路如下：

• 排序预处理：先对数组排序，这是双指针能工作的前提，也方便去重。
• 固定第一个数：遍历数组，固定第一个数nums[i]。
• 双指针找剩下两个数：在i后面的区间[i+1, len-1]中，用左右指针left和right寻找和为和nums[i]加起来为0的两个数。
• 指针移动规则：
  • 三数之和sum = 0：找到解，记录，然后跳过重复元素，两指针同时向中间移动
    • 这一步要进行去重，一定要找到解后再去重，避免出现第二个相同的解
    • 这一步目的不是为了让同一个元组的数字不重复，而是为了避免出现两个相同的元素，也就是之前出现过的元组不可以再出现第二次了
  • 三数之和sum < 0：和太小，左指针右移（增大和）
  • 三数之和sum > 0：和太大，右指针左移（减小和）
• 去重处理：
  • 外层循环跳过相同的nums[i]，避免重复的三元组开头
  • 找到解后，跳过相同的nums[left]和nums[right]，避免相同的三元组

【代码】

我写的代码，因为懒得加注释了，所以注释是AI加上的

/* 2-力扣15-三数之和 Author：郑龙浩 Date：2026-03-13 算法：哈希 或 双指针 思路： 1. 排序数组，方便去重和双指针移动 2. 固定第一个数i，在i后面用双指针left和right寻找剩下两数 3. 当三数之和等于0时，记录结果并移动指针 4. 当三数之和大于0时，right左移（减小和） 5. 当三数之和小于0时，left右移（增大和） 注意：求的元组是组合不是排列，需要去重 刚开始想用哈希表去做，发现如果输出的是这种三元组出现的数量有多少个， 哈希表是很好去写的，但是如果是出现的元组具体是那些个，就很难写了，我就放弃了 然后去用的双指针去写的 这里的双指针有点像「二分查找」，但是不太一样 用时：47min */#include"bits/stdc++.h"usingnamespacestd;// 有两种去重的方法，保留其中一种就OKclassSolution{public:vector<vector<int>>threeSum(vector<int>&nums){vector<vector<int>>ans;// 存储结果三元组intlen=nums.size(),sum;// 数组长度，三数之和// 第一步：先排序，方便去重和双指针sort(nums.begin(),nums.end());// 外层循环，固定第一个数for(inti=0;i<len;i++){// 去重方法1：用if判断跳过重复的i// 原理：如果当前i和前一个i相同，那么这个i能组成的组合前一个i已经覆盖了// if (i > 0 && nums[i] == nums[i - 1]) continue;intleft=i+1;// 左指针，从i后面开始intright=len-1;// 右指针，从末尾开始// 内层双指针循环，寻找剩下两数while(left<right){sum=nums[i]+nums[left]+nums[right];// 计算三数之和if(sum==0){// 找到符合条件的三元组ans.push_back({nums[i],nums[left],nums[right]});// 记录后，移动指针继续寻找left++;right--;// 对left去重：跳过和当前left相同的值// 注意：比较的是left和left-1，因为上面已经left++了while(left<right&&nums[left]==nums[left-1])left++;// 对right去重：跳过和当前right相同的值// 注意：比较的是right和right+1，因为上面已经right--了while(left<right&&nums[right]==nums[right+1])right--;}elseif(sum>0){// 和太大，需要减小right--;// 移动右指针}else{// sum < 0，和太小，需要增大left++;// 移动左指针}}// 去重方法2：用while跳过重复的i// 这里用while让i停在最后一个相同值，for循环的i++会将其移到下一个不同值// 我个人更习惯这种写法，逻辑更清晰while(i+1<len&&nums[i]==nums[i+1])i++;}returnans;}};intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);return0;}

3-力扣18-四数之和

题目难度：中等
算法：双指针

【题目】

给你一个由n个整数组成的数组nums，和一个目标值target。请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]]（若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a、b、c和d互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按任意顺序返回答案 。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

提示：

• 1 <= nums.length <= 200
• -109 <= nums[i] <= 109
• -109 <= target <= 109

【思路】

和力扣15-三数之和是一样的思路

唯一的不同就是「多加了一个for循环」

主要的思路就是写两层循环，i 和 j 代表元组第一个和第二个，然后用双指针去寻找第三个和第四个

思路和前面是相同的

而且这两个题都要注意：去重，必须要去重，也就是要避免之前出现过的元组不可以再出现了

【代码】

我写的代码，因为懒得加注释了，所以注释是AI加上的

/* 3-力扣18-四数之和 Author：郑龙浩 Date：2026-03-13 算法：排序 + 双指针 思路： 1. 排序，方便去重和双指针移动 2. 固定前两个数i和j 3. 在i和j之后用双指针left和right寻找剩下两数 4. 注意去重和防止溢出 用时：30min */#include"bits/stdc++.h"usingnamespacestd;classSolution{public:vector<vector<int>>fourSum(vector<int>&nums,inttarget){vector<vector<int>>ans;// 存储结果intlen=nums.size();sort(nums.begin(),nums.end());// 先排序，方便去重和双指针// 第一层循环，固定第一个数for(inti=0;i<len-3;i++){// 第二层循环，固定第二个数for(intj=i+1;j<len-2;j++){intleft=j+1;// 左指针intright=len-1;// 右指针// 双指针寻找剩下两数while(left<right){// 计算四数之和，用long long防止溢出longlongsum=(longlong)nums[i]+nums[j]+nums[left]+nums[right];if(sum==target){// 找到符合条件ans.push_back({nums[i],nums[j],nums[left],nums[right]});// 找到后，移动指针继续寻找left++;right--;while(left<right&&nums[left]==nums[left-1])left++;// 对left去重，避免出现重复元组，也就是之前已经求出的元组不可以再有了while(left<right&&nums[right]==nums[right+1])right--;// 对right去重，避免出现重复元组，也就是之前已经求出的元组不可以再有了}elseif(sum>target){// 和太大，需要减小right--;// 移动右指针}else{// 和太小，需要增大left++;// 移动左指针}}// 对j去重：跳过相同值的j// 这里用while让j停在最后一个相同值，for循环的j++会将其移到下一个不同值while(j+1<len&&nums[j]==nums[j+1])j++;}// 对i去重：跳过相同值的i// 同样用while让i停在最后一个相同值，for循环的i++会将其移到下一个不同值while(i+1<len&&nums[i]==nums[i+1])i++;}returnans;// 返回所有不重复的四元组}};intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);return0;}

4-力扣344-反转字符串

题目难度：简答
算法/技巧：没有技巧

【题目】

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组s的形式给出。

不要给另外的数组分配额外的空间，你必须**原地修改输入数组**、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = ["h","e","l","l","o"] 输出：["o","l","l","e","h"]

示例 2：

输入：s = ["H","a","n","n","a","h"] 输出：["h","a","n","n","a","H"]

提示：

• 1 <= s.length <= 105
• s[i]都是 ASCII 码表中的可打印字符

【思路】

很简单的一个题，直接简单的双指针前后走就OK完活

【代码】

/* 4-力扣344-反转字符串 Author：郑龙浩 Date：2026-03-13 算法：1min 50s 用时：无 */#include"bits/stdc++.h"usingnamespacestd;classSolution{public:voidreverseString(vector<char>&s){intlen=s.size();intleft=0,right=len-1;chartemp;while(left<right){temp=s[left];s[left]=s[right];s[right]=temp;left++,right--;}}};intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);return0;}

5-力扣541-反转字符串II

题目难度：简单
算法/技巧：

【题目】

给定一个字符串s和一个整数k，从字符串开头算起，每计数至2k个字符，就反转这2k字符中的前k个字符。

• 如果剩余字符少于k个，则将剩余字符全部反转。
• 如果剩余字符小于2k但大于或等于k个，则反转前k个字符，其余字符保持原样。

示例 1：

**输入：**s = “abcdefg”, k = 2
输出：“bacdfeg”

示例 2：

**输入：**s = “abcd”, k = 2
输出：“bacd”

提示：

• 1 <= s.length <= 104
• s仅由小写英文组成
• 1 <= k <= 104

【思路】

没什么思路，就是注意边界的处理，边界的处理我刚开始有问题

【代码】

/* 5-力扣541-反转字符串II Author：郑龙浩 Date：2026-03-13 算法：没什么算法，就是写的时候很麻烦，对于边界处理，特别容易出错，所以改了好久 */#include"bits/stdc++.h"usingnamespacestd;classSolution{public:stringreverseStr(string s,intk){intcount=0;intlen=s.size();for(inti=0;i<len;i++){count++;if(count==k*2){for(intleft=i-(2*k-1),right=left+k-1;left<right;left++,right--){swap(s[left],s[right]);}count=0;}}if(count>0&&count<k){for(intleft=len-count,right=len-1;left<right;left++,right--)swap(s[left],s[right]);}elseif(count>=k&&count<2*k){for(intleft=len-count,right=left+k-1;left<right;left++,right--)swap(s[left],s[right]);}returns;}};intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);return0;}