454.四数相加II
题目链接：力扣
思路
题目中要求的是求满足nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0的情况有多少种，对数组元素的下标顺序并没有要求，那么可以将这四个元素进行两两拆分，nums1[i] + nums2[j] 和 nums3[k] + nums4[l] ，这种情况就相当于两数之和啦
注意是记录所有出现过的情况，不是某一种，所以用result全局记录
四数相加II
第一步：创建Map数组集合，key用来存放前两个数组的元素和，value用来存放和出现过的次数
第二步：遍历前两个数组，将和：出现过的次数存放发哦Map集合中
第三步：遍历后两个数组，将满足条件的情况记录到result中。（一开始的时候，我在这里犯了个错误：以为map集合中某个和记录的出现的次数就是全部的次数，其实不是的，只是满足情况的次数，有可能其他的和也满足这种情况的，所以要定义一个作用域更大的变量result来整体记录）
class Solution { public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { // 创建Map数组 Map<Integer,Integer> maps = new HashMap<>(); int result = 0; // 遍历nums1和nums2求出每个两个元素的和出现的次数 for (int i : nums1) { for (int j : nums2) { // 两数之和 int sum1 = i + j; maps.put(sum1,maps.getOrDefault(sum1,0) + 1); } } // 遍历nums3和nums4求出每个两个元素的和,查找map中是否存在对应的值 for (int i : nums3) { for (int j : nums4) { int temp = 0 - i- j; if (maps.containsKey(temp)) { result += maps.get(temp); } } } return result; } }
383. 赎金信
题目链接：力扣
思路
这个题目其实和242.有效的字母异位词很像，都在是一个字符串中查找另一个字符串的字符是否出现过，只不过242.有效的字母异位词题目的条件是所有的字符都是小写字母，这种情况用字符编码和数组下标对应做哈希函数，用数组做哈希表，因为字符出现的情况可以固定下来
这道383. 赎金信题目的条件是所有的字符，你不知道会出现什么字符，所以使用Map集合记录起来更加合适，先使用集合记录magazine种所有字符出现的情况，再遍历ransomNote，一旦ransomNote中map.get(ch)出现了<0的情况，说明ransomNote中出现了magazine没有的字符或者magazine中没有出现过这么多，就返回false
赎金信
第一步：创建Map集合
第二步：遍历magazine，记录字符和每个字符出现次数
第三步：遍历ransomNote，将Map集合中对应字符出现的次数减去，如果出现了次数<0的字符，就返回false
class Solution { public boolean canConstruct(String ransomNote, String magazine) { // 先遍历magaize Map<Character,Integer> map = new HashMap<>(); for (int i = 0 ; i < magazine.length() ; i++) { char ch = magazine.charAt(i); map.put(ch,map.getOrDefault(ch,0) + 1); } // 再遍历ransomNote for (int i = 0 ; i < ransomNote.length() ; i++) { char ch = ransomNote.charAt(i); map.put(ch,map.getOrDefault(ch,0) - 1); if (map.get(ch) < 0) { return false; } } return true; } }
15. 三数之和
题目链接：力扣
思路
哈希法：从原理上来说，这道题和两数之和一样，两数之和要求的是在一个数组中找出两个数之和等于目标值，而且这个结果是唯一的。这道题是一个数组中找出三个数之和等于目标值，但是结果是不唯一的，而且还不能重复，这就很麻烦了，会牵扯到去重问题
所以使用哈希法的话去重会很困难，搞不明白，这道题更适合使用排序+双指针
排序+双指针：首先数组进行排序，只有排序后才能更好地使用指针进行数地相加，假设有个数组{-1，0，1，2，-1，-4}，排序后是{-4，-1，-1，0，1，2}。
假设i、left、right三个指针分别指向a、b、c三个数字。i 是for循环遍历自动产生的指针，然后起初left指向i后面的一位，right指向最后一位，因为数组是排序后的，在 i 指向的时候，如果目前三个数字的和大于0，就向前移动right，那么这个和就小了，如果目前三个数字的和小于0，i无法移动，只能等下一轮循环，那就向后移动left，这个数就变大了，这是采用双指针的基本思想。
接下来，要处理三个数字的去重操作：
a的去重操作：
a就是 i ，是循环时遍历元素的下标，那我们如果去重的话一般就是判断nums[i] == nums[i + 1], 但是我们此时 i + 1 指向的是left ，如果用这个条件判断成三数中不能有重复的了，而不是a 不能有重复的了， 所以这里应该使用nums[i] == nums[i - 1] 进行判断，用下面的图进行距离
b和c的去重操作：
当我们收割到符合条件的结果的时候，如果不进行去重，可能会出现多个相同的结果，所以我们left和right会造成的相同结果进行去重，去重之后将两个指针再移动到一位进行比较
收割结果，去重，移动指针
三数之和
排序+双指针
第一步：创建接收集合，对数组进行排序
第二步：遍历数组，有了指针i
第三步：对指针 i 进行去重操作
第四步：创建left 和 right 指针
第五步：移动指针，找到符合条件的元素
第六步：如果找到，收割结果，对left和right进行去重操作
第七步：继续移动指针寻找符合条件的元组
class Solution { public List<List<Integer>> threeSum(int[] nums) { // 创建集合收割结果 List<List<Integer>> result = new ArrayList<>(); // 对数组进行排序 Arrays.sort(nums); // 遍历数组 for (int i = 0 ; i < nums.length ; i++) { // 如果排序后的数组nums[i]就大于0,那就不可能再出现要求的结果了 if (nums[i] > 0) { return result; } // 对i指向的a进行去重 if (i > 0 && nums[i] == nums[i - 1]) { continue; } // 定义left指针和right指针 int left = i + 1; int right = nums.length - 1; while (left < right) { // 求三个指针指向的数的和 int sum = nums[i] + nums[left] + nums[right]; if (sum > 0) { right--; } else if (sum < 0) { left++; } else { // 收割符合条件的数组 result.add(Arrays.asList(nums[i],nums[left],nums[right])); // 对right指针指向的c元素进行去重 while (right > left && nums[right] == nums[right - 1]) {right--;} // 对left指针指向的b元素进行去重 while (right > left && nums[left] == nums[left + 1]) {left++;} right--; left++; } } } return result; } }
18. 四数之和
题目链接：力扣
思路
四树之和延续了三叔之和的思路，四树之和其实是在三数之和的基础上再外层再套了一层循环
需要注意的细节：
1、因为这个题目时自定义target,所以不能像三数之和那样进行剪枝操作
2、i 进行剪枝操作的时候要将 k 和 i 看成是一个整体
3、i 进行去重的时候，应该是 i > k + 1
4、因为数字之和比较大，所以数据类型应该选择long，而且要对和进行强转，因为java中字面量默认时int类型
四数之和
排序+双指针
第一步：创建接收集合，对数组进行排序
第二步：遍历第一个元素，对k进行剪枝和去重
第三步：遍历第二个元素，对i进行剪枝和去重
第四步：定义left和right指针
第五步：移动指针，找到符合条件的元素
第六步：如果找到，收割结果，对left和right进行去重操作
第七步：继续移动指针寻找符合条件的元组
class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { // 创建接收集合 List<List<Integer>> result = new ArrayList<>(); // 对数组进行排序 Arrays.sort(nums); for (int k = 0 ; k < nums.length ; k++) { // 剪枝操作 // 因为这里的target不是0,也有可能数组中全是负数，所以不能像三数之和一样进行剪枝 if (nums[k] > target && nums[k] > 0 && target > 0) { break; } // 去重操作 if (k > 0 && nums[k] == nums[k-1]) { continue; } for (int i = k + 1 ; i < nums.length ; i++) { // 剪枝操作 // 这里剪枝去重的话k和i是一个整体 if (nums[k] + nums[i] > target && nums[k] + nums[i] > 0 && target > 0) { break; } // 去重操作 if (i > k + 1 && nums[i] == nums[i - 1]) { continue; } // 定义left和right指针 int left = i + 1; int right = nums.length - 1; while (right > left) { long sum = (long)nums[k] + nums[i] + nums[left] + nums[right]; if (sum > target) { right--; } else if (sum < target) { left++; } else { // 收割结果 result.add(Arrays.asList(nums[k],nums[i],nums[left],nums[right])); // 去重操作 while (right > left && nums[right] == nums[right - 1]) { right--; } while (right > left && nums[left] == nums[left + 1]) { left++; } // 移动指针 right--; left++; } } } } return result; } }
