2024.02.23

leetcode15:三数之和

思路：

暴力法可考虑三重循环，但应该超时了，这里使用排序+双指针，排序时间复杂度为O(nlogn)，遍历时间复杂度为O(n)，每一个下标的遍历中双指针遍历其后面数组的时间复杂度为O(n)，因此遍历的总时间复杂度为O(n^2)，该思路的时间复杂度为O(n^2)。

1、对数组从小到大排序；

2、对于排序后的数组，从前向后遍历，分3种情况：

(1)若对于nums[i] > 0，则直接结束遍历，因为i之后的数更大，导致三个数的和不可能为0，只能为正数;

(2)若i > 0时nums[i] == nums[i - 1]，则跳过，因为后续数组和为-nums[i]的情况在num[i - 1]处可能已经处理了；

(3)反之，使用双指针的思想，令l = i + 1, r = n - 1(n为所传入数组长度)，当l < r时进行while循环，若nums[i] + nums[l] + nums[r] == 0，则记录者三个数到list集合中，同时要进行去重(坑点)，当nums[l] == nums[l + 1]时，说明左指针向右移动时存在重复值，因此l++，直到不满足nums[l] == nums[l + 1]，右指针同理，当nums[r - 1] == nums[r]时，说明右指针向左移动时存在重复值，因此r--，直到不满足nums[r - 1] == nums[r]，找到重复值的最后一个后，再执行一次l++和r--(若只移动左或右时，则只有一侧的值发生改变，肯定三数和不为0)；若nums[i] + nums[l] + nums[r] < 0，则移动左指针l++，使得左指针处值更大；若nums[i] + nums[l] + nums[r] > 0，则移动右指针r--，使得右指针处值更小。

直接将一堆同类型的值定义为List的方法：Arrays.asList(value1, value2, value3)，则会得到list类型列表:[value1, value2, value3]

下午要去玩，后续待更。。。。。。

布隆过滤器：

用于解决Redis缓存穿透，其原理如下：

入数据库数据时，使用布隆过滤器做个标记，然后在用户请求到来时，业务线程确认缓存失效后，可以通过查询布隆过滤器快速判断数据是否存在，如果不存在，就不用通过查询数据库来判断数据是否存在。

布隆过滤器是由一个固定大小的二进制向量或者位图和一系列映射函数组成的，对于位数组，在初始状态时，它所有位置都被置为0，当一个元素加入布隆过滤器中的时候，会进行如下操作：

1、使用布隆过滤器中的n个哈希函数对元素值进行计算，得到n个哈希值；

2、根据得到的哈希值，在位数组中把对应下标的值置为 1（若哈希值为hash1，位数组长度为m，则将位数组下标为hash1 % m的位置标为1）

当需要查询元素时：

1、对给定元素再次进行相同的哈希计算；

2、得到哈希值之后判断位数组中对应的点位的每个元素是否都为 1，如果值都为 1，那么说明这个值存在布隆过滤器当中，如果存在一个值不为 1，说明该元素不在布隆过滤器中；

上述方法可能出现误判的情况，其原因是：

1、不同查询值得到的hash值相同（如value1、value2经过哈希计算后，得到的hash值均为h1，但数据库中进存在value1或value2）；

2、经过运算得到点位上的 1 是多个不同的变量经过运算后得到的（如value1经过计算后的点位为3、4、5，但value2经过计算后的点位为3、4，value3经过计算后的点位为5，此时数据库只存在value2、value3，不存在value1，误判value1存在）

若经过布隆过滤器查询后确定不存在，则数据库中一定不存在，不会误判（因为哈希值无法匹配上）；反之若布隆过滤器查询后确定存在，数据库中不一定存在，可能出现误判。