Skip to content

Latest commit

 

History

History
532 lines (448 loc) · 15.5 KB

0454.四数相加II.md

File metadata and controls

532 lines (448 loc) · 15.5 KB
Raw

参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们受益！

需要哈希的地方都能找到map的身影

第454题.四数相加II

力扣题目链接

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

为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。

例如:

输入:

  • A = [ 1, 2]
  • B = [-2,-1]
  • C = [-1, 2]
  • D = [ 0, 2]

输出:

2

解释:

两个元组如下:

  1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
  2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

算法公开课

《代码随想录》算法视频公开课：学透哈希表，map使用有技巧！LeetCode：454.四数相加II，相信结合视频再看本篇题解，更有助于大家对本题的理解。

思路

本题乍眼一看好像和0015.三数之和，0018.四数之和差不多，其实差很多。

本题是使用哈希法的经典题目，而0015.三数之和，0018.四数之和并不合适使用哈希法，因为三数之和和四数之和这两道题目使用哈希法在不超时的情况下做到对结果去重是很困难的，很有多细节需要处理。

而这道题目是四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑有重复的四个元素相加等于0的情况，所以相对于题目18. 四数之和，题目15.三数之和，还是简单了不少！

如果本题想难度升级：就是给出一个数组（而不是四个数组），在这里找出四个元素相加等于0，答案中不可以包含重复的四元组，大家可以思考一下，后续的文章我也会讲到的。

本题解题步骤：

  1. 首先定义 一个unordered_map，key放a和b两数之和，value 放a和b两数之和出现的次数。
  2. 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中。
  3. 定义int变量count，用来统计 a+b+c+d = 0 出现的次数。
  4. 再遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。
  5. 最后返回统计值 count 就可以了

C++代码:

class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        unordered_map<int, int> umap; //key:a+b的数值，value:a+b数值出现的次数
        // 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中
        for (int a : A) {
            for (int b : B) {
                umap[a + b]++;
            }
        }
        int count = 0; // 统计a+b+c+d = 0 出现的次数
        // 再遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就把map中key对应的value也就是出现次数统计出来。
        for (int c : C) {
            for (int d : D) {
                if (umap.find(0 - (c + d)) != umap.end()) {
                    count += umap[0 - (c + d)];
                }
            }
        }
        return count;
    }
};
  • 时间复杂度: O(n^2)
  • 空间复杂度: O(n^2)，最坏情况下A和B的值各不相同，相加产生的数字个数为 n^2

其他语言版本

Java：

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int res = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        //统计两个数组中的元素之和，同时统计出现的次数，放入map
        for (int i : nums1) {
            for (int j : nums2) {
                int sum = i + j;
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
        }
        //统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数
        for (int i : nums3) {
            for (int j : nums4) {
                res += map.getOrDefault(0 - i - j, 0);
            }
        }
        return res;
    }
}

Python：

（版本一） 使用字典

class Solution(object):
    def fourSumCount(self, nums1, nums2, nums3, nums4):
        # 使用字典存储nums1和nums2中的元素及其和
        hashmap = dict()
        for n1 in nums1:
            for n2 in nums2:
                if n1 + n2 in hashmap:
                    hashmap[n1+n2] += 1
                else:
                    hashmap[n1+n2] = 1
        
        # 如果 -(n1+n2) 存在于nums3和nums4, 存入结果
        count = 0
        for n3 in nums3:
            for n4 in nums4:
                key = - n3 - n4
                if key in hashmap:
                    count += hashmap[key]
        return count

（版本二） 使用字典

class Solution(object):
    def fourSumCount(self, nums1, nums2, nums3, nums4):
        # 使用字典存储nums1和nums2中的元素及其和
        hashmap = dict()
        for n1 in nums1:
            for n2 in nums2:
                hashmap[n1+n2] = hashmap.get(n1+n2, 0) + 1
        
        # 如果 -(n1+n2) 存在于nums3和nums4, 存入结果
        count = 0
        for n3 in nums3:
            for n4 in nums4:
                key = - n3 - n4
                if key in hashmap:
                    count += hashmap[key]
        return count

（版本三）使用 defaultdict

from collections import defaultdict 
class Solution:
    def fourSumCount(self, nums1: list, nums2: list, nums3: list, nums4: list) -> int:
        rec, cnt = defaultdict(lambda : 0), 0
        for i in nums1:
            for j in nums2:
                rec[i+j] += 1
        for i in nums3:
            for j in nums4:
                cnt += rec.get(-(i+j), 0) 
        return cnt

Go：

func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {  
    m := make(map[int]int)  
    count := 0  
  
    // 构建nums1和nums2的和的map  
    for _, v1 := range nums1 {  
        for _, v2 := range nums2 {  
            m[v1+v2]++  
        }  
    }  
  
    // 遍历nums3和nums4，检查-c-d是否在map中  
    for _, v3 := range nums3 {  
        for _, v4 := range nums4 {  
            sum := -v3 - v4  
            if countVal, ok := m[sum]; ok {  
                count += countVal  
            }  
        }  
    }  
  
    return count  
}

JavaScript:

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number[]} nums3
 * @param {number[]} nums4
 * @return {number}
 */
var fourSumCount = function(nums1, nums2, nums3, nums4) {
    const twoSumMap = new Map();
    let count = 0;
    // 统计nums1和nums2数组元素之和，和出现的次数，放到map中
    for(const n1 of nums1) {
        for(const n2 of nums2) {
            const sum = n1 + n2;
            twoSumMap.set(sum, (twoSumMap.get(sum) || 0) + 1)
        }
    }
    // 找到如果 0-(c+d) 在map中出现过的话，就把map中key对应的value也就是出现次数统计出来
    for(const n3 of nums3) {
        for(const n4 of nums4) {
            const sum = n3 + n4;
            count += (twoSumMap.get(0 - sum) || 0)
        }
    }

    return count;
};

TypeScript：

function fourSumCount(nums1: number[], nums2: number[], nums3: number[], nums4: number[]): number {
    let helperMap: Map<number, number> = new Map();
    let resNum: number = 0;
    let tempVal: number | undefined;
    for (let i of nums1) {
        for (let j of nums2) {
            tempVal = helperMap.get(i + j);
            helperMap.set(i + j, tempVal ? tempVal + 1 : 1);
        }
    }
    for (let k of nums3) {
        for (let l of nums4) {
            tempVal = helperMap.get(0 - (k + l));
            if (tempVal) {
                resNum += tempVal;
            }
        }
    }
    return resNum;
};

PHP:

class Solution {
    /**
     * @param Integer[] $nums1
     * @param Integer[] $nums2
     * @param Integer[] $nums3
     * @param Integer[] $nums4
     * @return Integer
     */
    function fourSumCount($nums1, $nums2, $nums3, $nums4) {
        $map = [];
        foreach ($nums1 as $n1) {
            foreach ($nums2 as $n2) {
                $temp = $n1 + $n2;
                $map[$temp] = isset($map[$temp]) ? $map[$temp]+1 : 1;
            }
        }
        $count = 0;
        foreach ($nums3 as $n3) {
            foreach ($nums4 as $n4) {
                $temp = 0 - $n3 - $n4;
                if (isset($map[$temp])) {
                    $count += $map[$temp];
                }
            }
        }
        return $count;
    }
}

Swift：

func fourSumCount(_ nums1: [Int], _ nums2: [Int], _ nums3: [Int], _ nums4: [Int]) -> Int {
    // ab和: ab和出现次数
    var countDic = [Int: Int]()
    for a in nums1 {
        for b in nums2 {
            let key = a + b
            countDic[key] = countDic[key, default: 0] + 1
        }
    }

    // 通过-(c + d)作为key，去累加ab和出现的次数
    var result = 0
    for c in nums3 {
        for d in nums4 {
            let key = -(c + d)
            result += countDic[key, default: 0]
        }
    }
    return result
}

Rust：

use std::collections::HashMap;
impl Solution {
    pub fn four_sum_count(nums1: Vec<i32>, nums2: Vec<i32>, nums3: Vec<i32>, nums4: Vec<i32>) -> i32 {
        let mut umap:HashMap<i32, i32> = HashMap::new();
        for num1 in &nums1 {
            for num2 in &nums2 {
                *umap.entry(num1 + num2).or_insert(0) += 1;
            }
        }
        
        let mut count = 0;
        
        for num3 in &nums3 {
            for num4 in &nums4 {
                let target:i32 = - (num3 + num4);
                count += umap.get(&target).unwrap_or(&0);          
            }
        }
        
        count
     }
}

Scala:

object Solution {
  // 导包
  import scala.collection.mutable
  def fourSumCount(nums1: Array[Int], nums2: Array[Int], nums3: Array[Int], nums4: Array[Int]): Int = {
    // 定义一个HashMap，key存储值，value存储该值出现的次数
    val map = new mutable.HashMap[Int, Int]()
    // 遍历前两个数组，把他们所有可能的情况都记录到map
    for (i <- nums1.indices) {
      for (j <- nums2.indices) {
        val tmp = nums1(i) + nums2(j)
        // 如果包含该值，则对他的key加1，不包含则添加进去
        if (map.contains(tmp)) {
          map.put(tmp, map.get(tmp).get + 1)
        } else {
          map.put(tmp, 1)
        }
      }
    }
    var res = 0 // 结果变量
    // 遍历后两个数组
    for (i <- nums3.indices) {
      for (j <- nums4.indices) {
        val tmp = -(nums3(i) + nums4(j))
        // 如果map中存在该值，结果就+=value
        if (map.contains(tmp)) {
          res += map.get(tmp).get
        }
      }
    }
    // 返回最终结果，可以省略关键字return
    res
  }
}

C#：

public int FourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
       Dictionary<int, int> dic = new Dictionary<int, int>();
        foreach(var i in nums1){
            foreach(var j in nums2){
                int sum = i + j;
                if(dic.ContainsKey(sum)){
                    dic[sum]++;
                }else{
                    dic.Add(sum, 1);
                }
                
            }
        }
        int res = 0;
         foreach(var a in nums3){
            foreach(var b in nums4){
                int sum = a+b;
                if(dic.TryGetValue(-sum, out var result)){
                    res += result;
                }
            }
        }
        return res;
    }

C：

// 哈希表大小
const int HASH_SIZE = 101;

typedef struct node {
    int val;
    int count;
    struct node *next;
} node, *HashMap;

// 哈希表插入
void hash_insert(HashMap hashmap[], int val) {
    int idx = val < 0 ? (-val) % HASH_SIZE : val % HASH_SIZE, count = 0;
    node *p = hashmap[idx];
    while (p->next != NULL) {
        p = p->next;
        if (p->val == val) {
            (p->count)++;
            return;
        }
    }
    node *new = malloc(sizeof(node));
    new->val = val;
    new->count = 1;
    new->next = NULL;
    p->next = new;
    return;
}

// 哈希表查找
int hash_search(HashMap hashmap[], int val) {
    int idx = val < 0 ? (-val) % HASH_SIZE : val % HASH_SIZE;
    node *p = hashmap[idx];
    while (p->next != NULL) {
        p = p->next;
        if (p->val == val) return p->count;
    }
    return 0;
}

int fourSumCount(int* nums1, int nums1Size, int* nums2, int nums2Size, int* nums3, int nums3Size, int* nums4, int nums4Size){
    // 初始化哈希表
    HashMap hashmap[HASH_SIZE];
    for (int i = 0; i < HASH_SIZE; i++) {
        hashmap[i] = malloc(sizeof(node));
        hashmap[i]->next = NULL;
    }
    
    // 统计两个数组元素之和的负值和出现的次数，放到哈希表中
    int count = 0, num;
    for (int i = 0; i < nums1Size; i++) {
        for(int j = 0; j < nums2Size; j++) {
            num = - nums1[i] - nums2[j];
            hash_insert(hashmap, num);
        }
    }
    
    // 统计另外两个数组元素之和，查找哈希表中对应元素的出现次数，加入总次数
    for (int i = 0; i < nums3Size; i++) {
        for(int j = 0; j < nums4Size; j++) {
            num = nums3[i] + nums4[j];
            count += hash_search(hashmap, num);
        }
    }
    return count;
}

Ruby:

# @param {Integer[]} nums1
# @param {Integer[]} nums2
# @param {Integer[]} nums3
# @param {Integer[]} nums4
# @return {Integer}
# 新思路：和版主的思路基本相同，只是对后面两个数组的二重循环，用一个方法调用外加一重循环替代，简化了一点。
#       简单的说，就是把四数和变成了两个两数和的统计（结果放到两个 hash 中），然后再来一次两数和为0.
#       把四个数分成两组两个数，然后分别计算每组可能的和情况，分别存入 hash 中，key 是 和，value 是 数量；
#       最后，得到的两个 hash 只需要遍历一次，符合和为零的 value 相乘并加总。
def four_sum_count(nums1, nums2, nums3, nums4)
    num_to_count_1 = two_sum_mapping(nums1, nums2)
    num_to_count_2 = two_sum_mapping(nums3, nums4)

    count_sum = 0

    num_to_count_1.each do |num, count|
        count_sum += num_to_count_2[-num] * count # 反查另一个 hash，看有没有匹配的，没有的话，hash 默认值为 0，不影响加总；有匹配的，乘积就是可能的情况
    end

    count_sum
end

def two_sum_mapping(nums1, nums2)
    num_to_count = Hash.new(0)

    nums1.each do |num1|
        nums2.each do |nums2|
            num_to_count[num1 + nums2] += 1 # 统计和为 num1 + nums2 的有几个
        end
    end

    num_to_count
end