454.四数相加II
这道题做之前就知道了需要用到哈希表，但是绞尽脑汁还是没有想出来该怎么做。最后还是看了Carl的视频解析才想明白，原来是要把四个数组，两两进行for loop，这有点分而治之的意思。我是呆板的一直想着四个for loop进行计算呢。这也拓宽了我的思路，希望以后可以想到用这个办法来做类似的题。
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int,int> umap;
int res = 0;
for(int i=0; i<nums1.size(); i++){
for(int j=0; j<nums2.size();j++){
int cur_sum = nums1[i] + nums2[j];
auto it = umap.find(cur_sum);
if(it != umap.end()){
(it->second)++;
}
else{
umap.emplace(make_pair(cur_sum,1));
}
}
}
for(int i=0; i<nums3.size();i++){
for(int j=0; j<nums4.size();j++){
int cur_sum = nums3[i] + nums4[j];
int need = 0 - cur_sum;
auto it = umap.find(need);
if(it != umap.end()){
res = res + it->second;
}
}
}
return res;
}
};
383. 赎金信
这道题倒是不难，而且我先试着用上一题Carl写的简洁代码用在for loop和添加哈希表数据上，但是没考虑到减去哈希表的单位时，应该检查该单位的剩余数量是否大于0。第一遍写的时候没有考虑这件事，以为是简洁代码本身出了问题，用我朴素的写法写的时候才想到这点。以下是朴素版和简洁版。（比较奇怪的事是：简洁版的所需时间和空间不知道为什么会比朴素版要长一点呢）
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
unordered_map<char,int> umap;
for(int m=0; m<magazine.length(); m++){
auto it = umap.find(magazine[m]);
if(it != umap.end()){
(it->second)++;
}
else{
umap.emplace(make_pair(magazine[m],1));
}
}
for(int n=0; n<ransomNote.length(); n++){
auto it = umap.find(ransomNote[n]);
if(it != umap.end() && (it->second)>0){
(it->second)--;
}
else{
return false;
}
}
return true;
}
};
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
unordered_map<char,int> umap;
for(char m:magazine){
umap[m]++;
}
for(char n:ransomNote){
auto it = umap.find(n);
if(it != umap.end() && (it->second)>0){
(it->second)--;
}
else{
return false;
}
}
return true;
}
};
随后又看了Carl的解法，发现真的是还能再优秀一些。他没用哈希表，而是创建了一个长度为26的数组。因为本题只会出现小写字母，所以最多就是26个，然后再记录一共出现几次就可以了。这个方法其实在昨天的题里也用了类似的解法，可我没自己写一遍。这回自己也照着写了一遍，希望以后自己也可以想起来要这么写。而且Carl还加了ransomNote和magazine的大小比较，因为如果ransomNote大于magazine，那必定找不出来结果。优化真的很美好啊。
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int sum[26] = {0};
if(ransomNote.length() > magazine.length())
return false;
for(int i=0;i<magazine.length(); i++){
sum[magazine[i]-'a']++;
}
for(int j=0;j<ransomNote.length(); j++){
if(sum[ransomNote[j]-'a'] < 1)
return false;
else
sum[ransomNote[j]-'a'] --;
}
return true;
}
};
15. 三数之和
这道题我想的是利用两个指针，一个指向左边，一个指向右边，然后for loop里的来遍历left和right中间的值，以这样的方式去寻找相加等于0的数组。虽然本题Carl的解法也是用了左右的双指针，但其实很不一样。也说明我的解法不是可行的。
本题的思路应该是先将数组排序（这步我想到了），然后在for loop里i从最左遍历到最后，在每个loop中，设定left为i+1，right为size-1，然后left和right往中间靠。
为了去重，一旦发现当前的i所指的值和之前(i-1)的值一样，那就跳过这个loop。因为(i-1)和目前i的值一样，在上一个loop里，我们已经把这个值应有的组合加入到result里了。而不应该是发现如果i的值等于i+1的值就跳过loop，那样的话，答案还没加到result里。
然后我们就该在left < right 这个条件下进行while loop，如果left和right和i所指的值>0的话，就该right往左移，亦而反之。如果三个值相加等于0，那么就说明我们找到了一个合适的set。不知道为什么，我的第一反应总是试图判断(i+left)是大于还是小于right来决定如何移动left和right。明明sum(left+right+i)的值更符合题意，更直观(我脑子里应该想的是算两个数的绝对值对比另一个数，但是那样其实更麻烦，因为那样【0，1，1】这种就过不了)。 在加入和合适的set后，我们还应该进行一步去重。因为如果下一个left或者下一个right和当前的它们对应的值一样的话，我们就不应该再把这个值放到result里。我们应该跳过重复的值，直到遇到新的left和right的值。
这道题还需要多做很多遍，一定要彻底理解该怎么做。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<vector<int>> res;
for(int i=0; i<nums.size()-2; i++){
if(nums[i] > 0)
return res;
if((i>0) && (nums[i] == nums[i-1]))
continue;
int left = i+1;
int right = nums.size()-1;
while(left < right){
if((nums[i] + nums[left] + nums[right]) < 0)
left++;
else if ((nums[i] + nums[left] + nums[right]) > 0)
right--;
else{
vector<int> cur_res = {nums[i],nums[left],nums[right]};
res.push_back(cur_res);
while((left<right) && (nums[right] == nums[right-1]))
right--;
while((left<right) && (nums[left] == nums[left+1]))
left++;
left++;
right--;
}
}
}
return res;
}
};
18. 四数之和
这道题我其实就是还用的3sum的逻辑，把这道题给做出来了，算是默写了一遍3sum。中途经历了溢出的问题，看了Carl的解决法，把类型改成了long就好了。
class Solution {
public:
void threeSum(vector<int>& nums, int i, int need, int target){
for(int j=i+1; j<nums.size()-2; j++){
if((j>i+1) && (nums[j] == nums[j-1])){
continue;
}
else{
int left = j+1;
int right = nums.size()-1;
while(left < right){
if((long)nums[left]+nums[j]+nums[right] > need){
right--;
}
else if((long)nums[left]+nums[j]+nums[right] < need){
left++;
}
else{
vector<int> temp_res = {nums[i],nums[left],nums[j],nums[right]};
res.push_back(temp_res);
while((left < right) && (nums[left] == nums[left+1]))
left++;
while((left < right) && (nums[right] == nums[right-1]))
right--;
left++;
right--;
}
}
}
}
}
vector<vector<int>> fourSum(vector<int>& nums, int target) {
if(nums.size()<4)
return res;
sort(nums.begin(),nums.end());
for(int i=0; i<nums.size(); i++){
if((i>0) && (nums[i-1] == nums[i]))
continue;
else{
int need = target - nums[i];
threeSum(nums,i,need,target);
}
}
return res;
}
private:
vector<vector<int>> res;
};
