哈希unordered_map lc454 四数相加II

本题是目前遇到时间复杂度最高的题目，核心思路主要分成两部分，第一部分是将四个数组两两分组，每组用两层for循环遍历，也是导致时间复杂度为\(O(n^2)\)的关键。第二部分与[[day6#unordered_map lc1 两数之和|leetcode第一题两数之和]]思路大体一致。

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int,int> map;
        for(int n1 : nums1){
            for(int n2 : nums2){
                map[n1+n2]++;
            }
        }

        int count = 0;
        for(int n3 : nums3){
            for(int n4 : nums4){
                if(map.find(0-n3-n4) != map.end()){
                    count += map[0-n3-n4];
                }
            }
        }
        return count;
    }
};

哈希数组 lc383 赎金信

这道题目与[[day6#哈希数组 lc242 有效的字母异位词|leetcode第242题有效的字母异位词]]很像，因为范围可控且较小，使用数组进行哈希性能更好，时间复杂度\(O(n)\)，空间复杂度\(O(1)\)。

三个for

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int alpha[26]{0};
        for(auto c : magazine){
            alpha[c-'a']++;
        }
        for(auto c : ransomNote){
            alpha[c-'a']--;
        }
        for(int count : alpha){
            if (count < 0){
                return false;
            }
        }
        return true;
    }
};

代码随想录答案 两个for

这个写法优化了一些，理论上效率更高

// 时间复杂度: O(n)
// 空间复杂度：O(1)
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int record[26] = {0};
        //add
        if (ransomNote.size() > magazine.size()) {
            return false;
        }
        for (int i = 0; i < magazine.length(); i++) {
            // 通过recode数据记录 magazine里各个字符出现次数
            record[magazine[i]-'a'] ++;
        }
        for (int j = 0; j < ransomNote.length(); j++) {
            // 遍历ransomNote，在record里对应的字符个数做--操作
            record[ransomNote[j]-'a']--;
            // 如果小于零说明ransomNote里出现的字符，magazine没有
            if(record[ransomNote[j]-'a'] < 0) {
                return false;
            }
        }
        return true;
    }
};

双指针 lc15 三数之和

双指针

这道题虽然用哈希也能做，但是去重非常麻烦，双指针更好理解一点。整体思路如下

• 先对数组进行从小到大排序
• 用i历遍数组，i要找的是返回的三个数中最小数字的下标
• 这里就要对i进行去重，且i要和前一个数字比较，即nums[i] != num[i-1]，不用后一个数字比较是因为后一个数字是接下来要用的双指针中的左指针，下标i对应的值可以与双指针指向的值相等
• 接下来定义左右指针，左指针初始值为i+1，右指针初始值为数组最后一个元素，左指针要一直小于右指针，因为数组中每个数字在求和时只能使用一次
• 遍历时若求和大于0，右指针需要向左移。
• 遍历时若求和小于0，左指针需要向右移。
• 若求和等于0，则找到了一组答案，接下来需要对左右指针进行去重
  以上方法的时间复杂度为\(O(n^2)\)。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size()-2;i++){
            if(nums[i] > 0) return result;
            if(i>0 && nums[i]==nums[i-1]){
                continue;
            }
            int left = i+1;
            int right = nums.size()-1;
            while(left<right){
                int sum = nums[i]+nums[left]+nums[right];
                if(sum>0){
                    right--;
                }
                else if(sum<0){
                    left++;
                }
                else{
                    result.push_back(vector<int>{nums[i],nums[left],nums[right]});
                    while(left<right && nums[left] == nums[left+1]){
                        left++;
                    }
                    while(left<right && nums[right] == nums[right-1]){
                        right--;
                    }
                    left++;
                    right--;
                }
            }
        }
        return result;
    }
};

对于这个解法，我本来以为可以有些优化的方法。经过尝试，以下两种失败

1. 在找到一组答案并对左右指针去重时将

while(left<right && nums[left] == nums[left+1]){
    left++;
}
while(left<right && nums[right] == nums[right-1]){
	right--;
}

改为

while(nums[left] == nums[left+1]){
    left++;
}
while(nums[right] == nums[right-1]){
	right--;
}

本来是想反正每次循环都会判断左小于右，就算去掉也不会多进一次循环。但是这样在遇到从结尾向前有连续相同元素的数组时会越界，如[0,0,0]。

2. 每次成功找到一组答案并移动i时，改变right的初始值

本来想的是i和left总会变大，那么对应的是否应该将right的初始值变小。
答案是否定的，因i和left变大是相对于历遍i时的初始值，相对于返回的答案，并不一定。考虑这个例子[-4,-3,-1,0,4]。像这样初始i+left过小时，这种思路就不成立了。

双指针 lc18 四数之和

这道题核心解法和三数之和类似，难点在于剪枝。

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(),nums.end());
        for (int i=0;i<nums.size();i++){
            //cout<<"i "<<nums[i]<<endl;
            if(nums[i]>target && nums[i]>=0){
                //cout<<"case1"<<endl;
                break;
            }
            if(i>0 && nums[i]==nums[i-1]){
                continue;
            }
            for(int j=i+1;j<nums.size();j++){
                cout<<"j "<<nums[j]<<endl;
                if(nums[i]+nums[j]>target && nums[j]>=0){
                    //cout<<"i "<<nums[i]<<" j "<<nums[j]<<endl;
                    //cout<<"case2"<<endl;
                    break;
                }
                if(j>i+1 && nums[j]==nums[j-1]){
                    continue;
                }
                int left = j+1;
                int right = nums.size()-1;
                while(left<right){
                    if((long)nums[i]+nums[j]+nums[left]+nums[right]>target){
                        right--;
                    }
                    else if((long)nums[i]+nums[j]+nums[left]+nums[right]<target){
                        left++;
                    }
                    else{
                        result.push_back({nums[i],nums[j],nums[left],nums[right]});
                        while(left<right && nums[left] == nums[left+1]) left++;
                        while(left<right && nums[right] == nums[right-1]) right--;
                        left++;
                        right--;
                    }
                }
            }
        }
        //cout<<"case3"<<endl;
        return result;
    }
};

三数之和，四数之和看起来都像是哈希能做的题目，但是使用哈希去重时要小心。所以这些题目关键点在判断用双指针还是哈希。