← All notes

Leetcode记录：哈希表例题

Table of contents

• 续哈希表例题
• Leetcode 454
• Leetcode 15

续哈希表例题

四数之和 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;
}

Python 实现

from collections import Counter

def four_sum_count(a, b, c, d):
    pair_sums = Counter(x + y for x in a for y in b)
    return sum(pair_sums[-x - y] for x in c for y in d)

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

三数之和

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;
}

Python 实现

# 本题仅使用 Python 内置功能，无需额外 import。
def three_sum(nums):
    nums.sort()
    answer = []
    for i, value in enumerate(nums):
        if i and value == nums[i - 1]:
            continue
        left, right = i + 1, len(nums) - 1
        while left < right:
            total = value + nums[left] + nums[right]
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                answer.append([value, nums[left], nums[right]])
                left, right = left + 1, right - 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1
    return answer

四数之和

给你一个由 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;
}

Python 实现

# 本题仅使用 Python 内置功能，无需额外 import。
def four_sum(nums, target):
    nums.sort()
    answer = []
    for i in range(len(nums) - 3):
        if i and nums[i] == nums[i - 1]:
            continue
        for j in range(i + 1, len(nums) - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue
            left, right = j + 1, len(nums) - 1
            while left < right:
                total = nums[i] + nums[j] + nums[left] + nums[right]
                if total == target:
                    answer.append([nums[i], nums[j], nums[left], nums[right]])
                    left, right = left + 1, right - 1
                    while left < right and nums[left] == nums[left - 1]: left += 1
                    while left < right and nums[right] == nums[right + 1]: right -= 1
                elif total < target:
                    left += 1
                else:
                    right -= 1
    return answer

• 数据结构与算法