454.四数相加II
题目链接: 454. 四数相加 II - 力扣（LeetCode）
题目
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
- 0 <= i, j, k, l < n
- nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
示例 1：
输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2] 输出：2 解释： 两个元组如下： 1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0 2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
示例 2：
输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0] 输出：1
思路
本题是使用哈希法的经典题目，而 15.三数之和，18.四数之和 并不合适使用哈希法，因为 三数之和 和 四数之和 这两道题目使用哈希法在不超时的情况下做到对结果去重是很困难的，很有多细节需要处理。
而这道题目是四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑有重复的四个元素相加等于0的情况，所以相对于题目18. 四数之和，题目15.三数之和，还是简单了不少！
本题解题步骤：
- 首先定义 一个map，key放a和b两数之和，value 放 a 和 b 两数之和出现的次数。
- 遍历 大A 和 大B 数组，统计两个数组元素之和，和出现的次数，放到map中。
- 定义int变量count，用来统计 a+b+c+d = 0 出现的次数。
- 在遍历 大C 和 大D 数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。
- 最后返回统计值 count 就可以了
注意: 之所以选择先统计 大A 和 大B 两个元素之和，是因为这样才是时间复杂度(O(n^2))最低。如果先统计 大A 、 大B 和 大C 三个数组的和，只不过时间复杂度会大一点( O(n^3) )。
代码
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Map<Integer, Integer> map = new HashMap<>();
int temp;
int res = 0;
//统计两个数组中的元素之和，同时统计出现的次数，放入map
for (int i : nums1) {
for (int j : nums2) {
temp = i + j;
if (map.containsKey(temp)) {
map.put(temp, map.get(temp) + 1);
} else {
map.put(temp, 1);
}
}
}
//统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数
for (int i : nums3) {
for (int j : nums4) {
temp = i + j;
if (map.containsKey(0 - temp)) {
res += map.get(0 - temp);
}
}
}
return res;
}
}
383. 赎金信
题目链接: 383. 赎金信 - 力扣（LeetCode）
题目
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
示例 1：
输入：ransomNote = "a", magazine = "b" 输出：false
示例 2：
输入：ransomNote = "aa", magazine = "ab" 输出：false
示例 3：
输入：ransomNote = "aa", magazine = "aab" 输出：true
思路
暴力法: 两层for循环，不断去寻找。
哈希法: 本题判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成。也就是看字符串ransom中的元素，是否在magazine中出现过。
在集合中判断一个元素是否出现过，则立即想到哈希法。
题目中还有两点细节需要注意：
magazine中的每个字符只能在ransomNote中使用一次。ransomNote和magazine由小写英文字母组成
因为不可以重复使用，所以我们需要在建立哈希表的时候，统计每个元素出现的次数，因为字符串中只有小写字母，小写字母最多只有26种，所以可以用长度为26的数组来作哈希表。
采用空间换取时间的哈希策略， 用一个长度为26的数组记录magazine里字母出现的次数。
然后再用ransomNote去验证这个数组是否包含了ransomNote所需要的所有字母。
代码
1 class Solution {
2 public boolean canConstruct(String ransomNote, String magazine) {
3 // 定义一个哈希映射数组
4 int[] record = new int[26];
5
6 // 遍历
7 for(char c : magazine.toCharArray()){
8 record[c - 'a'] += 1;
9 }
10
11 for(char c : ransomNote.toCharArray()){
12 record[c - 'a'] -= 1;
13 }
14
15 // 如果数组中存在负数，说明ransomNote字符串总存在magazine中没有的字符
16 for(int i : record){
17 if(i < 0){
18 return false;
19 }
20 }
21
22 return true;
23 }
24 }
15. 三数之和
题目链接: 15. 三数之和 - 力扣（LeetCode）
题目
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1] 输出：[] 解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0] 输出：[[0,0,0]] 解释：唯一可能的三元组和为 0 。
思路
哈希法: 这道题目可以像两数之和一样使用哈希法，但是有一个巨大的难点，就是元组不可以重复，所以说需要做去重操作，而去重的操作中有超级多的细节需要注意，在面试中很难写出bug free的代码。
双值针法: 虽然说哈希法也是时间复杂度为O(n^2)的算法，但是双指针法会比哈希法更加高效。
具体步骤:
1、首先将数组从小到大排序，然后有一层for循环，i从下标0的地方开始，同时定一个下标left 定义在 i+1 的位置上，定义下标 right 在数组结尾的位置上。
2、处理一下边界的逻辑， 如果nums[i]已经大于0，那么不可能凑成三数和为0，直接结束这个for循环。
3、i 元素的去重逻辑，应该是从第二个元素开始，如果和前面的元素一样的话，就直接略过当前的循环，进入下一个循环中。但这里很细节，如果写成，if（nums[i] == nums[i+1] )这种情况的话，当数组为[-1，-1,0,1,2]时，i = 0, nums[i] = -1; left = 1; right=4; 这种情况会忽略掉-1 -1 2 这种情况。所以说 i=0 不比较，从i=1开始，和前面的比较，如果相同，则跳过，这才是正确的i去重的办法，注意: 我们要做的是 不能有重复的三元组，但三元组内的元素是可以重复的！所以这里应该这么写：if (i > 0 && nums[i] == nums[i - 1])这么写就是当前使用 nums[i]，我们判断前一位是不是一样的元素，在看 [-1, -1 ,2] 这组数据，当遍历到 第一个 -1 的时候，只要前一位没有-1，那么 {-1, -1 ,2} 这组数据一样可以收录到 结果集里。这是一个非常细节的思考过程。
3、在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i] ，b = nums[left] ，c = nums[right]。
4、接下来如何移动left 和right呢，循环条件也应该是while（left<right)，因为如果两者相等，那相当于只有两个数了，不符合题意；
如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。
如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。
5、这个过程中，会找到三数之和等于0 的时刻，这时候，要先把它们加到result 里面去记录上，然后，在进行left和right的去重环节，这时候是拿下一个和现在的这个相比较，因为这个是已经加进去了，所以不会遗漏。
代码
时间复杂度：O(n^2)
1 class Solution {
2 public List<List<Integer>> threeSum(int[] nums) {
3 List<List<Integer>> result = new ArrayList<>();
4 Arrays.sort(nums);
5 // 找出a + b + c = 0
6 // a = nums[i], b = nums[left], c = nums[right]
7 for (int i = 0; i < nums.length; i++) {
8 // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
9 if (nums[i] > 0) {
10 return result;
11 }
12
13 if (i > 0 && nums[i] == nums[i - 1]) { // 去重a
14 continue;
15 }
16
17 int left = i + 1;
18 int right = nums.length - 1;
19 while (right > left) {
20 int sum = nums[i] + nums[left] + nums[right];
21 if (sum > 0) {
22 right--;
23 } else if (sum < 0) {
24 left++;
25 } else {
26 result.add(Arrays.asList(nums[i], nums[left], nums[right]));
27 // 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
28 while (right > left && nums[right] == nums[right - 1]) right--;
29 while (right > left && nums[left] == nums[left + 1]) left++;
30
31 right--;
32 left++;
33 }
34 }
35 }
36 return result;
37 }
38 }
思考
既然三数之和可以使用双指针法，那么上面的1.两数之和，可不可以使用双指针法呢？
两数之和 不能使用双指针法，因为1.两数之和 要求返回的是索引下标， 而双指针法一定要排序，一旦排序之后原数组的索引就被改变了。
如果 1.两数之和 要求返回的是数值的话，就可以使用双指针法了。
18. 四数之和
题目链接: 18. 四数之和 - 力扣（LeetCode）
题目
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
- 0 <= a, b, c, d < n
- a、b、c 和 d 互不相同
- nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
输入：nums = [2,2,2,2,2], target = 8 输出：[[2,2,2,2]]
思路
四数之和，和三数之和是一个思路，都是使用双指针法, 基本解法就是在它的基础上再套一层for循环。
三数之和 的双指针解法是一层for循环num[i]为确定值，然后循环内有left和right下标作为双指针，找到nums[i] + nums[left] + nums[right] == 0。
四数之和 的双指针解法是两层for循环nums[i] + nums[j]为确定值，依然是循环内有left和right下标作为双指针，找出nums[i] + nums[j] + nums[left] + nums[right] == target的情况，三数之和的时间复杂度是O(n^2)，四数之和的时间复杂度是O(n^3) 。
注意
1、不能判断nums[k] > target 就返回了，三数之和 可以通过 nums[i] > 0 就返回了，因为 0 已经是确定的数了，四数之和这道题目 target是任意值。比如：数组是[-4, -3, -2, -1]，target是-10，不能因为-4 > -10而跳过。但是我们依旧可以去做剪枝，逻辑变成 nums[i] > target && (nums[i] >=0 || target >= 0)就可以了。
2、同样的道理也可以用在二级剪枝上，将nums[i]+ nums[j] 看作整体，剪枝条件 nums[k] + nums[i] > target && nums[k] + nums[i] >= 0 可以优化为 nums[k] + nums[i] > target && nums[i] >= 0。
因为只要 nums[k] + nums[i] > target，那么 nums[i] 后面的数都是正数的话，就一定 不符合条件了。
代码
1 class Solution {
2 public List<List<Integer>> fourSum(int[] nums, int target) {
3 List<List<Integer>> result = new ArrayList<>();
4 Arrays.sort(nums);
5
6 for (int i = 0; i < nums.length; i++) {
7
8 // nums[i] > target 直接返回, 剪枝操作
9 if (nums[i] > 0 && nums[i] > target) {
10 return result;
11 }
12
13 if (i > 0 && nums[i - 1] == nums[i]) { // 对nums[i]去重
14 continue;
15 }
16
17 for (int j = i + 1; j < nums.length; j++) {
18
19 if (j > i + 1 && nums[j - 1] == nums[j]) { // 对nums[j]去重
20 continue;
21 }
22
23 int left = j + 1;
24 int right = nums.length - 1;
25 while (right > left) {
26 // nums[k] + nums[i] + nums[left] + nums[right] > target int会溢出
27 long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
28 if (sum > target) {
29 right--;
30 } else if (sum < target) {
31 left++;
32 } else {
33 result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
34 // 对nums[left]和nums[right]去重
35 while (right > left && nums[right] == nums[right - 1]) right--;
36 while (right > left && nums[left] == nums[left + 1]) left++;
37
38 left++;
39 right--;
40 }
41 }
42 }
43 }
44 return result;
45 }
46 }
思考
- 在三数之和中，双指针法就是将原本暴力O(n^3)的解法，降为O(n^2)的解法，四数之和的双指针解法就是将原本暴力O(n^4)的解法，降为O(n^3)的解法。那么一样的道理，五数之和、六数之和等等都采用这种解法；
- 之前我们讲过哈希表的经典题目，四数相加，相对于本题简单很多，因为本题是要求在一个集合中找出四个数相加等于target，同时四元组不能重复；而四数相加是四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑有重复的四个元素相加等于0的情况，所以相对于本题还是简单了不少！
双指针法的总结
双指针法将时间复杂度：O(n^2)的解法优化为 O(n)的解法。也就是降一个数量级，题目如下：
27.移除元素
15.三数之和
18.四数之和
链表相关双指针题目：
206.反转链表
19.删除链表的倒数第N个节点
面试题 02.07. 链表相交
142题.环形链表II
双指针法在字符串题目中还有很多应用，后面还会介绍到。