liujiyu
Liujiyu's blog
learn & record

Leetcode记录：哈希表例题

续哈希表例题

四数之和 I

Leetcode 454. 给你四个整数数组 nums1,nums2,nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

  1. 0 <= i, j, k, l < n
  2. nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

可以将四个数组分成两部分，A 和 B 为一组，C 和 D 为另外一组。 对于 A 和 B，我们使用二重循环对它们进行遍历，得到所有 A[i]+B[j] 的值并存入哈希映射中。对于哈希映射中的每个键值对，每个键表示一种 A[i]+B[j]，对应的值为 A[i]+B[j] 出现的次数。 对于 C 和 D，我们同样使用二重循环对它们进行遍历。当遍历到 C[k]+D[l] 时，如果 −(C[k]+D[l]) 出现在哈希映射中，那么将 −(C[k]+D[l]) 对应的值累加进答案中。最终即可得到满足 A[i]+B[j]+C[k]+D[l]=0 的四元组数目:

int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
    unordered_map<int, int> countAB;
    for (int u: A) {
        for (int v: B) {
            ++countAB[u + v];
        }
    }
    int ans = 0;
    for (int u: C) {
        for (int v: D) {
            if (countAB.count(-u - v)) {
                ans += countAB[-u - v];
            }
        }
    }
    return ans;
}

如果是要求不重复的话，利用哈希表将会很困难：

三数之和

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

「不重复」的本质是需要保证：

  1. 第二重循环枚举到的元素不小于当前第一重循环枚举到的元素；
  2. 第三重循环枚举到的元素不小于当前第二重循环枚举到的元素。

也就是说，我们枚举的三元组 (a,b,c) 满足 a≤b≤c，保证了只有 (a,b,c) 这个顺序会被枚举到，而 (b,a,c)、(c,b,a) 等等这些不会，这样就减少了重复。要实现这一点，我们可以将数组中的元素从小到大进行排序，随后使用普通的三重循环就可以满足上面的要求。 同时，对于每一重循环而言，相邻两次枚举的元素不能相同，否则也会造成重复。

如果我们固定了前两重循环枚举到的元素 a 和 b，那么只有唯一的 c 满足 a+b+c=0。当第二重循环往后枚举一个元素 b’时，由于 b’>b，那么满足 a+b’+c‘=0 的 c’一定有 c’< c，即 c’在数组中一定出现在 c 的左侧。也就是说，我们可以从小到大枚举 b，同时从大到小枚举 c，也就是双指针的思想，这样就将三重循环降低为二重循环了。

在代码实现中一定要注意需要在哪里去重，否则可能会出现一些算例不会ac的情况。

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(),nums.end());
    vector<vector<int>> ans;
    for(int i = 0; i <nums.size()-2;++i){
        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 {
                ans.push_back({nums[i],nums[left],nums[right]});
                left++;
                while(nums[left] == nums[left-1] && left < right)
                    left++;
                right--;
                while(nums[right] == nums[right+1] && right > left)
                    right--;
            }
        }
    }
    return ans;
}

四数之和

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

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

求解思路和三数之和一模一样：

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    if(nums.size()<4) 
        return vector<vector<int>>{};
    sort(nums.begin(), nums.end());
    vector<vector<int>> ans;
    for(int i = 0; i < nums.size()-3; ++i){
        if(nums[i] > 0 && nums[i]> target)
            break;
        if (i>0 && nums[i] == nums[i-1])
            continue;
        for(int j = i+1; j < nums.size()-2; ++j){
            if(nums[j] > 0 && nums[j]+nums[i] > target){
                break;
            }
            if(j>i+1 && nums[j] == nums[j-1])
                continue;
            int left = j+1;
            int right = nums.size()-1;
            while(left < right){
                int a =nums[i];
                int b = nums[j];
                int c = nums[left];
                int d = nums[right];
                if(c > 0 && a+b+c >= target)
                    break;
                if((long)a+b+c+d < target)
                    left++;
                else if((long)a+b+c+d > target)
                    right--;
                else{
                    ans.push_back({a,b,c,d});
                    right--;
                    left++;
                    while(left < right && nums[right] == nums[right+1])
                    right--;
                    while(left < right && nums[left] == nums[left-1])
                    left++;
                }
            }
        }
    }
    return ans;
}

Table of Contents