第18题. 四数之和
题目链接：第18题. 四数之和
题目描述：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
示例： 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集 合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
思路
四数之和本质还是和上提的三数之和一样，都是使用双指针法，就是在三数之和的基础上加上一层for循环。
细节：三数之和在开始以通过 nums[i] > 0 就返回了，因为 0 已经是确定的数了。
但是四数之和这道题目 target是任意值。有负数的存在，即不能因为-4 > -10而跳过。
应该是：nums[i] > target && (nums[i] >=0 || target >= 0)
四数之和的双指针解法：两层for循环nums[k] + nums[i]为确定值,然是循环内有left和right下标作为双指针，找出nums[k] + nums[i] + nums[left] + nums[right] == target的情况,三数之和的时间复杂度是O(n2)，四数之和的时间复杂度是O(n3) 。
代码实现
//四数之和怎么求？
给定数组 nums = [1, 0, -1, 0, -2, 2]，和
target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1],
[-2, -1, 1, 2], [-2, 0, 0, 2] ]
//与三数之和的思路一样，双层循环，一个是num k，一个是num i；
剪枝操作，
去重操作。
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target){
vector<vector<int>> result;
sort(begin(),end());//进行排序从小到大
for(int k = 0; k < nums.size(); k++){
//做剪枝操作 不能直接nums[k] > target
if(nums[k] > target && nums[k] >= 0){
break;
}
if(k > 0 && nums[k] == nums[k - 1]){//对numsk去重
//和三数之和的去重一致
continue;
}
for(int i = k + 1; i < nums.size(); i++){//i初始位置时在k的后一位
//做2级剪枝处理，把k和i作为一个整体进入下一个循环
if(nums[k] + nums[i] > target && nums[k]+nums[i] >= 0 ){
break;
}
//对numsi去重
if(i > k+1 && nums[i] == nums[i -1]){
continue;
}
//下面的操作就是移动left和right的操作
int left = i + 1;
int right = nums.size() - 1;
while(rig > left){
//如果四数加起来大于目标值，则rig减一 ，不然left加一
if ((long) nums[k] + nums[i] + nums[left] + nums[right] > target) {
right--;
} else if ((long) nums[k] + nums[i] + nums[left] + nums[right] < target) {
left++;
} else {//等于目标值的情况
result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
// 对nums[left]和nums[right]去重
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
// 找到答案时，双指针同时收缩
right--;
left++;
}
}
}
}
return result;
}
}
344.反转字符串
题目链接：344.反转字符串
题目描述：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出
示例 1：
输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]
示例 2：
输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
思路
在反转链表中，使用了双指针的方法。
那么反转字符串依然是使用双指针的方法，只不过对于字符串的反转，其实要比链表简单一些。
对于字符串，我们定义两个指针（也可以说是索引下标），一个从字符串前面，一个从字符串后面，两个指针同时向中间移动，并交换元素：
代码实现
//反转字符串
反转字符串依然是使用双指针的方法，只不过对于字符串的反转，其实要比链表简单一些
class Solution {
public:
void reverseString(vector<char>& s){
int length = nums.size();//定义一个长度
for(i = 0, j = length - 1; i < length / 2 ; i++, j--){
//ij分别是首尾指针，而 i < length / 2确保了length为奇数时中间值不动的情况
// 随后ij指针同时移动
swap(nums[i], nums[j]);//使用swap函数交换两个元素的数值
}
}}
541. 反转字符串II
题目链接：541. 反转字符串II
题目描述：给定一个字符串 s 和一个整数 k，从字符串开头算起, 每计数至 2k 个字符，就反转这 2k 个字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样
示例:
输入: s = "abcdefg", k = 2
输出: "bacdfeg"
思路
其实在遍历字符串的过程中，只要让 i += (2 * k)，i 每次移动 2 * k 就可以了，然后判断是否需要有反转的区间。
因为要找的也就是每2 * k 区间的起点，这样写，程序会高效很多。
所以当需要固定规律一段一段去处理字符串的时候，要想想在在for循环的表达式上做做文章。
代码如此
//反转字符串Ⅱ
//输入: s = "abcdefg", k = 2
//输出: "bacdfeg
class Solution {
public:
string reverseStr(string s, int k){
for(i = 0; i < s.size(); i += (2 * k)){//这里 i += (2 * k)即再遍历过程中，i每次移动2*k
//然后去判断是否有反转的区间
if(i + k < = s.size()){// 1. 每隔 2k 个字符的前 k 个字符进行反转
// 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
reverse(s.begin() + i, s.begin() + i + k);
} else{
// 3. 剩余字符少于 k 个，则将剩余字符全部反转。
reverse(s.begin() + i, s.end());
}
}
return s;
}}
那么我们也可以实现自己的reverse函数，其实和题目344. 反转字符串 (opens new window)道理是一样的。
下面我实现的reverse函数区间是左闭右闭区间，代码如下：
class Solution {
public:
void reverse(string& s, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
swap(s[i], s[j]);
}
}
string reverseStr(string s, int k) {
for (int i = 0; i < s.size(); i += (2 * k)) {
// 1. 每隔 2k 个字符的前 k 个字符进行反转
// 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
if (i + k <= s.size()) {
reverse(s, i, i + k - 1);
continue;
}
// 3. 剩余字符少于 k 个，则将剩余字符全部反转。
reverse(s, i, s.size() - 1);
}
return s;
}
};
哈希表总结
哈希表理论基础
-
一旦遇到要判断这个元素是否出现在集合里，则一般来说可以考虑哈希表解题
-
对于哈希表，要知道哈希函数和哈希碰撞在哈希表中的作用：哈希函数是把传入的key映射到符号表的索引上。哈希碰撞处理有多个key映射到相同索引上时的情景，处理碰撞的普遍方式是拉链法和线性探测法。
-
常见的三种哈希结构：
数组
set（集合）
map（映射） -
什么时候用std::set，什么时候用std::multiset，什么时候用std::unordered_set，都是很有考究的。
-
只有对这些数据结构的底层实现很熟悉，才能灵活使用，否则很容易写出效率低下的程序
-
map虽说yyds，但是有时很繁琐，复杂度高
哈希表经典题目
数组作为哈希表
242.有效的字母异位词-简单
383. 赎金信-简单
49. 字母异位词分组-中等
438. 找到字符串中所有字母异位词-中等
set作为哈希表
349. 两个数组的交集-简单
350.两个数组的交集 II-简单
第202题. 快乐数-简单