454. 四数相加 II

题目描述

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

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

解题思路

首先是一种愚蠢的做法，以为On2就是两个for循环

#![allow(unused)]
fn main() {
struct Solution {}

impl Solution {
    pub fn four_sum_count(nums1: Vec<i32>, nums2: Vec<i32>, nums3: Vec<i32>, nums4: Vec<i32>) -> i32 {
        let n = nums1.len();
        use std::collections::HashMap;
        let mut res = 0;
        let mut map3: HashMap<i32, usize> = HashMap::new();
        let mut map4: HashMap<i32, usize> = HashMap::new();
        for i in 0..n {
            *map3.entry(nums3[i]).or_default() += 1;
            *map4.entry(nums4[i]).or_default() += 1;
        }
        for i in 0..n {
            for j in 0..n {
                let mut target = - nums1[i] - nums2[j];
                for (&a, &b) in map3.iter() {
                    let d = target - a;
                    if map4.contains_key(&d) {
                        res += b * map4.get(&d).unwrap();
                    }
                }
            }
        }
        res as i32
    }
}
}

这里面白白浪费了i和j的和

学习感想

#![allow(unused)]


fn main() {
struct Solution {}


impl Solution {
    pub fn four_sum_count(nums1: Vec<i32>, nums2: Vec<i32>, nums3: Vec<i32>, nums4: Vec<i32>) -> i32 {
        let n = nums1.len();
        use std::collections::HashMap;
        let mut res = 0;
        let mut map: HashMap<i32, usize> = HashMap::new();
        for i in 0..n {
            for j in 0..n {
                let target = nums1[i] + nums2[j];
                *map.entry(target).or_default() += 1;
            }
        }
        for i in 0..n {
            for j in 0..n {
                let target = - nums3[i] - nums4[j];
                if map.contains_key(&target) {
                    res += map.get(&target).unwrap();
                }
            }
        }
        res as i32
    }
}
}

地一下子还是没有想到要用hashmap做，感觉可能是双指针

#![allow(unused)]
fn main() {
struct Solution {}

impl Solution {
    pub fn four_sum_count(nums1: Vec<i32>, nums2: Vec<i32>, nums3: Vec<i32>, nums4: Vec<i32>) -> i32 {
        use std::collections::HashMap;
        let mut map: HashMap<i32, usize> = HashMap::new();
        for a in nums1 {
            for &b in nums2.iter() {
                map.entry(a + b)
                    .and_modify(|x| *x += 1usize)
                    .or_insert(1usize);
            }
        }
        let mut res: usize = 0usize;
        for c in nums3 {
            for &d in nums4.iter() {
                map.entry(0i32 - c - d)
                    .and_modify(|&mut x| res += x);
            }
        }
        res as i32
    }
}
}