开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> Java知识库 -> ??导图整理数组6:四数组的四数之和详解Counter类实现哈希表计数力扣454?? -> 正文阅读

[Java知识库]??导图整理数组6:四数组的四数之和详解Counter类实现哈希表计数力扣454??

此专栏文章是对力扣上算法题目各种方法的总结和归纳,?整理出最重要的思路和知识重点并以思维导图形式呈现,?当然也会加上我对导图的详解.

目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解),?毕竟算法不是做了一遍就能完全记住的.?所以本文适合已经知道解题思路和方法,?想进一步加强理解和记忆的朋友,?并不适合第一次接触此题的朋友(可以根据题号先去力扣看看官方题解,?然后再看本文内容).

关于本专栏所有题目的目录链接,?刷算法题目的顺序/注意点/技巧,?以及思维导图源文件问题请点击此链接.?欢迎和博主一起打卡刷力扣算法,?博主同步更新了算法视频讲解?和?其他文章/导图讲解,?更易于理解,?欢迎来看!

0.导图整理

1.维数太高,?分治处理

2.Java中map的merge和getOrDefault方法

3.6?most_common([n])方法

3.7?subtract([iterable-or-mapping])方法

?题目链接:??https://leetcode-cn.com/problems/4sum-ii/

0.导图整理

1.维数太高,?分治处理

此题乍一看似乎和?四数之和?差不多,?但是本质上却有着很大的区别,?首先无论是?三数之和?还是?四数之和,?它们都是在一个数组上的操作,?本质上都是一维的,?同时它们都要求找到?不重复?的元组,?这就限制了我们不能简单的使用哈希表进行去重操作,?最终只能将数组排序后使用双指针的方法.

但是本题是?四个独立的数组,?相当于是?四个维度,?想在四个维度上使用双指针的方法显然是不现实的.?同时此题只要求我们找到所有4个元素的和为0的元组个数即可,?并没有要求是不重复的元组,?这样就简单了很多,?也是可以使用哈希表的方法的.

此题在使用哈希表的时候,?会遇到如下的三种情况:

1.HashMap存一个数组,如A。然后计算三个数组之和,如BCD。时间复杂度为：O(n)+O(n^3),得到O(n^3).

2.HashMap存三个数组之和,如ABC。然后计算一个数组,如D。时间复杂度为：O(n^3)+O(n),得到O(n^3).

3.HashMap存两个数组之和,如AB。然后计算两个数组之和,如CD。时间复杂度为：O(n^2)+O(n^2),得到O(n^2).

根据时间复杂度来看,?我们肯定选择第三种情况.

确定了使用的方法(哈希表)以及分类的方法(两两分组),?接下来就是代码的书写了.?此题和?两数之和?中使用的哈希表有着很大的区别,?在两数之和中,?我们需要的是满足条件的下标值,?所以在哈希表中的值存取的就是元组的下标值,?这点是很容易实现的.?但是在此题中我们需要的是所有满足元素的个数,?所以哈希表中的值应存取出现的次数.?这相对于只存下标是有点难度的.?这就涉及到下文要讲的几个方法和类了.

2.Java中map的merge和getOrDefault方法

统计出现的次数,?在java中可以使用map类中的两个方法进行实现.

一种是countAB.put(u?+?v,?countAB.getOrDefault(u?+?v,?0)?+?1),?这里比较重要的是getOrDefault(u?+?v,?0)方法,?它的含义是获得键u?+?v对应的值,?也就是出现的次数,?如果当然哈希表中未出现,?则返回默认值0.?通过后面的+1操作,?实现在现有次数上+1或者初始化次数为1,?然后将这个键值对放入到哈希表中.

另一种方法是countAB.merge(u+v,?1,?(old,new_)->old+1),?这里使用了merge方法,?从名字就可以看出是?合并?的意思,?也就是将新出现的键值对和原来已有的键值对进行合并,?形成新的键值对.?中间的1表示如果原来没有此键值对,?那么这个新键值对的值就是1(出现次数为1次).?最后的参数表示了新的值的相对于旧的值的变化情况,?这里就是+1的操作.?有一点要主要的是new_有个下划线,?因为在java中new是创建对象的关键词,?这里是为了区别开来.?这个函数的语法就是上文所示那样,?具体的操作情况都可以根据实际来更改.

3.Python中的Counter类

在Python中哈希表是利用dict()字典来实现的,?但毕竟不是专为哈希表设计的类,?也没有那么丰富的方法来使用.?但是Python中直接设计了能够对哈希对象进行计数的类,?并且在功能上更加优秀,?下面我们重点介绍一下这个类.?

3.1?简介

1.一个 Counter 是一个 dict 的子类, 用于计数可哈希对象。它是一个集合, 元素像字典键(key)一样存储, 它们的计数存储为值。计数可以是任何整数值, 包括0和负数.

2.通常字典方法都可用于 Counter 对象,除了有两个方法工作方式与字典并不相同
? ?fromkeys(iterable)这个类方法没有在 Counter 中实现
? ?update([iterable-or-mapping]是在原有的键值对上加上,而不是替换

sum(c.values())                 # total of all counts
c.clear()                       # reset all counts
list(c)                         # list unique elements
set(c)                          # convert to a set
dict(c)                         # convert to a regular dictionary
c.items()                       # convert to a list of (elem, cnt) pairs
Counter(dict(list_of_pairs))    # convert from a list of (elem, cnt) pairs
c.most_common()[:-n-1:-1]       # n least common elements
+c                              # remove zero and negative counts

3.2?初始化

元素从一个 iterable 被计数或从其他的 mapping (or counter)初始化

c = Counter()                           # a new, empty counter
c = Counter('gallahad')                 # a new counter from an iterable
c = Counter({'red': 4, 'blue': 2})      # a new counter from a mapping
c = Counter(cats=4, dogs=8)             # a new counter from keyword args

3.3?空的处理

Counter对象有一个字典接口,如果引用的键没有任何记录,就返回一个0,而不是弹出一个KeyError

c = Counter(['eggs', 'ham'])
c['bacon']                              # count of a missing element is zero
0

3.4?删除元素

设置一个计数为0不会从计数器中移去一个元素。使用 del 来删除它

c['sausage'] = 0                        # counter entry with a zero count
del c['sausage']                        # del actually removes the entry

3.5?elements()方法

返回一个迭代器, 其中每个元素将重复出现计数值所指定次。元素会按首次出现的顺序返回。如果一个元素的计数值小于1, elements()将会忽略它

c = Counter(a=4, b=2, c=0, d=-2)
sorted(c.elements())
['a', 'a', 'a', 'a', 'b', 'b']

3.6?most_common([n])方法

返回一个列表, 其中包含 n 个最常见的元素及出现次数, 按常见程度由高到低排序。如果 n 被省略或为 None, most_common()将返回计数器中的所有元素。计数值相等的元素按首次出现的顺序排序

Counter('abracadabra').most_common(3)
[('a', 5), ('b', 2), ('r', 2)]

3.7?subtract([iterable-or-mapping])方法

从迭代对象或映射对象减去元素。像dict.update()但是是减去, 而不是替换。输入和输出都可以是0或者负数

c = Counter(a=4, b=2, c=0, d=-2)
d = Counter(a=1, b=2, c=3, d=4)
c.subtract(d)
c
Counter({'a': 3, 'b': 0, 'c': -3, 'd': -6})

3.8?数学操作

提供了几个数学操作, 可以结合 Counter 对象, 以生产multisets (计数器中大于0的元素)。
加和减, 结合计数器, 通过加上或者减去元素的相应计数。
交集和并集返回相应计数的最小或最大值。
每种操作都可以接受带符号的计数, 但是输出会忽略掉结果为零或者小于零的计数

sum(c.values())                 # total of all counts
c.clear()                       # reset all counts
list(c)                         # list unique elements
set(c)                          # convert to a set
dict(c)                         # convert to a regular dictionary
c.items()                       # convert to a list of (elem, cnt) pairs
Counter(dict(list_of_pairs))    # convert from a list of (elem, cnt) pairs
c.most_common()[:-n-1:-1]       # n least common elements
+c                              # remove zero and negative counts

3.9?注意点

1.计数器主要是为了表达运行的正的计数而设计；但是, 小心不要预先排除负数或者其他类型

2.Counter 类是一个字典的子类,不限制键和值。值用于表示计数, 但你实际上可以存储任何其他值

3.most_common()方法在值需要排序的时候用

4.原地操作比如 c[key] += 1, 值类型只需要支持加和减。所以分数,小数,和十进制都可以用, 负值也可以支持。这两个方法update()和subtract()的输入和输出也一样支持负数和0

5.Multiset多集合方法只为正值的使用情况设计。输入可以是负数或者0, 但只输出计数为正的值。没有类型限制, 但值类型需要支持加, 减和比较操作

6.elements()方法要求正整数计数。忽略0和负数计数

4.总结

1.看到形如：A+B....+N=0的式子,要转换为(A+...T)=-((T+1)...+N)再计算,这个T的分割点一般是一半,特殊情况下需要自行判断。定T是解题的关键

2.dp一般不会超过二维, 这里都四维了, 维度太高, 需要分治

3.算法中间使用了map的新方法merge和getOrDefault, 相比较于传统的判断写法, 大大提高了效率

源码?

Python:?

class Solution:
    def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
        # Counter类是dict()子类, 用于计数可哈希对象
        # 它是一个集合,元素像字典键(key)一样存储,它们的计数存储为值
        countAB = collections.Counter(u + v for u in A for v in B)
        ans = 0
        for u in C:
            for v in D:
                if -u - v in countAB:
                    ans += countAB[-u - v]
        return ans

java:

class Solution {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        Map<Integer, Integer> countAB = new HashMap<Integer, Integer>();
        for (int u : A) {
            for (int v : B) {
                // 存储u+v的结果,不存在赋值为1,存在在原来基础上+1
                // 另一种表达countAB.merge(u+v, 1, (old,new_)->old+1);
                countAB.put(u + v, countAB.getOrDefault(u + v, 0) + 1);
            }
        }
        int ans = 0;
        for (int u : C) {
            for (int v : D) {
                if (countAB.containsKey(-u - v)) {
                    ans += countAB.get(-u - v);
                }
            }
        }
        return ans;
    }
}

感觉作者写的不错的, 别忘了点赞关注加收藏哦(一键三连)!你的支持会带给我极大的动力, 写出更多优秀文章!

我的更多精彩文章链接, 欢迎查看

各种电脑/软件/生活/音乐/动漫/电影技巧汇总(你肯定能够找到你需要的使用技巧)

力扣算法刷题根据思维导图整理笔记快速记忆算法重点内容(欢迎和博主一起打卡刷题哦)

计算机专业知识?思维导图整理

最值得收藏的?Python?全部知识点思维导图整理,?附带常用代码/方法/库/数据结构/常见错误/经典思想(持续更新中)

最值得收藏的?C++?全部知识点思维导图整理(清华大学郑莉版),?东南大学软件工程初试906科目

最值得收藏的?计算机网络?全部知识点思维导图整理(王道考研),?附带经典5层结构中英对照和框架简介

最值得收藏的?算法分析与设计?全部知识点思维导图整理(北大慕课课程)

最值得收藏的?数据结构?全部知识点思维导图整理(王道考研),?附带经典题型整理

最值得收藏的?人工智能导论?全部知识点思维导图整理(王万良慕课课程)

最值得收藏的数值分析全部知识点思维导图整理(东北大学慕课课程)