力扣哈希表习题

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0

class Solution {
public:
    int fourSumCount(vector& nums1, vector& nums2, vector& nums3, vector& nums4) {
    	//定义map存放两个数组各个元素之和
        unordered_map m;
        for(auto n1:nums1){
            for(auto n2:nums2){
                m[n1+n2]++;
            }
        }

        int count=0;     //结果变量
		
		//对剩下两个元素各个元素之和进行查找
        for(auto n3 : nums3){
            for(auto n4 : nums4){
                if(m.find(0-n3-n4) != m.end()){
                    count += m[0-n3-n4];
                }
            }
        }
        return count;
    }
};

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

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int record[26]={0};     //定义一个数组，存放26个字母出现的次数

		//遍历一个string，统计各个字母出现的次数
        for(int i = 0;i 
15.三数之和 
双指针解法：先对数组进行排序，方便指针移动。固定第一个指针，接着使用left、right分别移动靠近
 
class Solution {
public:
    vector> threeSum(vector& nums) {
        if(nums.size() < 3){
            return {};
        }

        vector> res;
        //排序，方便后续的指针移动
        sort(nums.begin(), nums.end());

		//固定一个元素
        for(int i =0;i 0){
                return res;
            }
			
			//去重逻辑
            if(i > 0 && nums[i] == nums[i-1]){
                continue;
            }
			
			//定义左右指针
            int left = i+1;
            int right = nums.size()-1;
			
			//循环移动左右指针
            while(right > left){
                if(nums[i] + nums[left] + nums[right] > 0){
                    right--;
                }
                else if(nums[i] + nums[left] + nums[right] < 0){
                    left++;
                }
                else{
                    res.push_back(vector{nums[i], 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 res;
    }
};
 
18.四数之和 
首先排序，让移动的逻辑清楚。接着固定第一个和第二个数字，然后使用双指针移动寻找第三个、第四个数字。注意添加去重逻辑
 输入：nums = [1,0,-1,0,-2,2], target = 0
 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
 
class Solution {
public:
    vector> fourSum(vector& nums, int target) {
        if(nums.size() < 4){
            return {};
        }
        vector> res;
		//
        sort(nums.begin(),nums.end());
        for(int first = 0; first < nums.size()-3;++first){
            
            if(first > 0 && nums[first] == nums[first-1]){
                continue;
            }

            for(int second = first+1; second < nums.size()-2;++second){

                if(second > first + 1 && nums[second] == nums[second-1]){
                    continue;
                }

                int third = second+1;
                int four = nums.size()-1;
                while(third < four){
                    if(nums[first] + nums[second] > target-nums[third]-nums[four]){
                        four--;
                    }
                    else if(nums[first] + nums[second] < target-nums[third]-nums[four]){
                        third++;
                    }
                    else{
                        res.push_back(vector{nums[first] , nums[second] , nums[third] , nums[four]});

                        while(four > third && nums[four] == nums[four-1]){
                            four--;
                        }
                        while(third < four && nums[third] == nums[third + 1]){
                            third++;
                        }

                        third++;
                        four--;
                    }
                }

            }
        }
        return res;
    }
};
 
总结：有些题目使用数组作为简单的哈希表，比直接使用map更合适，但是数组的大小是受限的，有些情况下还是要用map，但是map需要维护红黑树，而且要做哈希运算，空间消耗更大。