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

-> Python知识库 -> 数组: 你还在用暴力法解两数之和吗? 力扣1 -> 正文阅读

[Python知识库]数组: 你还在用暴力法解两数之和吗? 力扣1

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

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

关于本专栏所有题目的目录链接,?刷算法题目的顺序/注意点/技巧,?以及思维导图源文件问题请点击此链接.?导图中源码在文章最后.

博主在公众号 [一起学计算机]每日首发力扣算法,?欢迎关注公众号每日和博主一起刷题!

博主在 B站?同步更新了?算法视频讲解?和?其他文章/导图讲解,?更易于理解,?欢迎来看!

0.导图整理

0.导图整理

1.暴力法

暴力法的思想很简单,?就是两层循环:?一层用来遍历所有元素,?另一层用来寻找目标数.

但此题中的注意点是题目中的:?假设每种输入只会对应一个答案. 但是, 数组中同一个元素不能使用两遍.

每种输入只对应一个输出?也就是要求我们找到满足的元素直接返回就可以了,?并不需要再去找其他满足的元素,?这也为下面使用哈希表的方法提供了前提,?因为如果需要找到所有满足的元素,?那么哈希表的结构就不能满足要求了.

数组中同一个元素不能使用两遍 这个要求就是代码中标注重点的部分 j?=?i?+?1;?的含义.?当遍历整个数组寻找 target - x 时, 需要注意到每一个位于 x 之前的元素都已经和 x 匹配过, 因此不需要再进行匹配.?而每一个元素不能被使用两次,?x本身也不需要进行匹配, 所以只需要在 x 后面的元素中寻找 target - x,?也就是从i+1开始遍历.

2.两遍哈希表

暴力法使用了两层循环,?时间复杂度达到了O(n^2),?而使用哈希表就可以将寻找目标数的操作降为O(1),?直接降了一个量级,?具体过程如下:?

使用了两次迭代。在第一次迭代中, 将每个元素的值和它的索引添加到表中。然后, 在第二次迭代中, 检查每个元素所对应的目标元素（target?nums[i]）是否存在于表中。注意, 该目标元素不能是 nums[i]本身！也就是?map.get(complement)?!=?i?的含义.

3.一遍哈希表

对于上面方法还有一点优化, 就是将两次迭代合并到一次中完成,?先进行匹配,?再插入到哈希表中!

首先创建一个哈希表, 对于每一个 x, 首先查询哈希表中是否存在 target - x,?如果存在直接返回结果就可以了.?之后将 x 插入到哈希表中, 即可保证不会让 x 和自己匹配,?因为在匹配时,?x还未插入到哈希表中.

这种优化对于时间复杂度没有太大影响,?但是代码看起来更简洁了.

4.哈希表中的循环和异议

对于使用哈希表的算法, 有人提出了异议, HashMap的containsKey里面还有一个循环, 也就还是O(n^2), map还增加了空间复杂度和开销, 综合来看还是暴力法最为有效, 但是这个观点也有点问题: 这个containsKey里的循环, 只有冲突了才会进入, 同时如果冲突频繁, 会改用getTreeNode方法去获取值, getTreeNode是从一棵红黑树中获取值, 时间复杂度顶多O(logN),?综合来看,?还是降低了时间复杂度.?对于红黑树感兴趣的朋友,?可以看博主的这篇思维导图.

5.java和Python中哈希表的差别

从上述代码可以看出,?两者对于哈希表的实现还是有很大的差别的.

首先java中的哈希表是用Map类实现的,?判断是否包含一个元素用的是?map.containsKey(Key)?函数,?获取?键?对应的?值?使用的是?map.get(Key)?函数,?插入到哈希表中使用的是?map.put(Key,?Value)

但是在Python中直接使用它自带的数据类型?字典dict?就实现了哈希表的操作,?并不需要新建类,?而且相应的操作也非常简单,?几乎不需要通过其他函数来实现.?判断是否包含一个元素用的是?in,?获取?键?对应的?值?使用的是?hashtable[Key]?函数,?插入到哈希表中使用的是?hashtable[Key] =?Value

仔细对比会发现,?Python语法是真的简洁明了,?这也是博主喜欢Python的原因.

这里补充说明一下Python中的?enumerate(nums)?函数,?简单来说就是对nums数组中的所有数添加了下标,?它返回的是?由下标和数据构成的二元元组,?在Python的for循环中还是挺经常使用的函数.

源码

Python:?

# 暴力法
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]

        return []


# 一遍哈希表
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = dict()
        for i, num in enumerate(nums):
            if target - num in hashtable:
                return [hashtable[target - num], i]
            hashtable[nums[i]] = i
        return []

java:?

// 暴力法
class Solution {
    public int[] twoSum(int[] nums, int target) {
         for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] == target - nums[i]) {
                    return new int[] { i, j };
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

//两遍哈希表
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement) && map.get(complement) != i) {
                return new int[] { i, map.get(complement) };
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

//一遍哈希表
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

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