算法总结与学习

[liang520]

知识点

1. 哈希表：在一般的多重循环中，可以通过建立哈希表，通过以空间换取速度的方式，我们可以将查找时间从 O(n)降低到 O(1)。
   比如:

• 列1

题目:
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9，因为 nums[0] + nums[1] = 2 + 7 = 9，所以返回 [0, 1]
解题:
一般的方式是多重循环暴力得出，比较好的方式是通过建立数字与索引位置的哈希表，一层循环迭代出来。最优的方法是迭代一遍，先把需要的结果计算出来，去哈希表中查找。如果没有，就把当前迭代的数字和键存起来，下一次迭代的时候，再如此循环。这样就是循环后面的值的时候，计算需要的数字，直接在哈希表中查找前面所存下来的值。