代码随想录算法训练营第七天| 454.四数相加II 383. 赎金信 15. 三数之和 18. 四数之和

复习一下哈希，哈希一般用于快速的判断是否有某一个元素出现。

454.四数相加II  

Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that:

0 <= i, j, k, l < n

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

#1 自己看到题目的第一想法    

想要nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0，即 nums1[i] + nums2[j] = – (nums3[k] + nums4[l]，循环i 和 j，得到两数之和，再循环 k 和 l，得到两数之和，将四数之和转为两数之和。

#2 看完代码随想录之后的想法   

思路都是对着的，但是记得之后注意一下本题和三数之和以及四数之和的差异。

383. 赎金信      

和 242.有效的字母异位词 是一个思路 ，算是拓展题，第六天已经做过，就不再重复了。

15. 三数之和             

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

#1 自己看到题目的第一想法       

这道题不同于454.四数相加II 是在四个array中取数字，本题是在同一个array中取三个数字。

一开始尝试用哈希，但是很难确保第三个数和前两个数的index不重合，同时map的value也很难确定是[i,j]还是key出现过的次数。

这道题之前做过，印象中记得是使用的双指针和一个for 循环，需要注意的点是不能有duplicate triplets，这个点做题的时候被卡了很久，难点在于需要判断 i 和 i – 1 位置的值而不是 i 和 i + 1 位置的值。

#2 看完代码随想录之后的想法    

如果是判断 nums[i] 与 nums[i + 1]是否一样，那就我们就把 三元组中出现重复元素的情况直接pass掉了。 例如{-1, -1 ,2} 这组数据，当遍历到第一个-1 的时候，判断 下一个也是-1，那这组数据就pass了。

我们要做的是 不能有重复的三元组，但三元组内的元素是可以重复的！

这么写就是当前使用 nums[i]，我们判断前一位是不是一样的元素，在看 {-1, -1 ,2} 这组数据，当遍历到 第一个 -1 的时候，只要前一位没有-1，那么 {-1, -1 ,2} 这组数据一样可以收录到 结果集里。

18. 四数之和   

#1 自己看到题目的第一想法    

这道题不同于454.四数相加II 是在四个array中取数字，本题是在同一个array中取四个数字。

本题和15. 三数之和几乎一样，只是将一个for循环改为两个for循环。

#2 收获   

对于15.三数之和 (opens new window)双指针法就是将原本暴力O(n^3)的解法，降为O(n^2)的解法，四数之和的双指针解法就是将原本暴力O(n^4)的解法，降为O(n^3)的解法。 

#3 类似题目

206.反转链表(opens new window)

19.删除链表的倒数第N个节点(opens new window)

160. 链表相交(opens new window)

142题.环形链表II