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

public static boolean canConstruct(String ransomNote, String magazine) {int[] magazineCount = new int[26];// 把magazine的字符出现的次数存放进数组for (int i = 0; i < magazine.length(); i++) {magazineCount[magazine.charAt(i) - 'a']++;}// 把ransomNote中出现的字符的对应的数组的值减1// 期间如果有某个值小于0，说明magazine中的字符无法满足ransomNote的组成for (int i = 0; i < ransomNote.length(); i++) {int temp = --magazineCount[ransomNote.charAt(i) - 'a'];if (temp < 0) {return false;}}return true;
}

15. 三数之和

建议：本题虽然和两数之和很像，也能用哈希法，但用哈希法会很麻烦，双指针法才是正解，可以先看视频理解一下双指针法的思路，文章中讲解的，哈希法很麻烦。

题目链接/文章讲解/视频讲解： 代码随想录

重点：

1. 双指针法

思路：

1. 双指针法

(1) 先把数组从小到大排序

(2) 从头开始遍历排序好的数组，如果i = i - 1，直接continue对 i 进行去重，并定义一个left = i + 1， right = nums.length - 1

(3) 不断的移动left和right，当i + left + right小于0时说明sum太小了，需要变大，因为是排序好的数组，直接把left++就可以把left移动到更大的数去了

(4) 不断的移动left和right，当i + left + right大于0时说明sum太大了，需要变小，因为是排序好的数组，直接把right--就可以把right移动到更小的数去了

(5) 当i + left + right等于0时，把这三个值存放到result中，接下来要对left和right分别去重。如果left = left + 1， left++。如果right = right - 1，right--

public static List<List<Integer>> threeSum(int[] nums) {// 先把数组从小到大排序Arrays.sort(nums);List<List<Integer>> result = new ArrayList<>();for (int i = 0; i < nums.length; i++) {// 如果i所指的数都已经大于0了，后面的数又都比它大，直接returnif (nums[i] > 0) {return result;}// 如果i所指的数和它前面的数相等，说明这个数已经被判断过了，continueif (i >= 1 && nums[i] == nums[i - 1]) {continue;}// 两个指针，一个指i + 1，一个指数组末尾int left = i + 1;int right = nums.length - 1;while (left < right) {int sum = nums[i] + nums[left] + nums[right];if (sum > 0) {// 当三数之和大于0时，证明需要减小，把right往前移一个right--;} else if (sum < 0) {// 当三数之和小于0时，证明需要变大，把left往后移一个left++;} else {// 当三数之和等于0时，需要对left和right所指的数分别去重result.add(Arrays.asList(nums[i], nums[left], nums[right]));while (left < right && nums[left + 1] == nums[left]) {left++;}while (left < right && nums[right - 1] == nums[right]) {right--;}// 为什么同时移动两个指针？// 因为如果只移动了right，你前面两数i和left都已经固定了，// 为了三数和为0，你right也相当于是固定的，// 也就是说i和left都已经判断过了，right也相当于判断过了。// 所以当上面的去重操作完成之后，left和right肯定同时移动的left++;right--;}}}return result;
}

18. 四数之和

建议： 要比较一下，本题和454. 四数相加II 的区别，为什么454.四数相加II 会简单很多，这个想明白了，对本题理解就深刻了。 本题思路整体和三数之和一样的，都是双指针，但写的时候有很多小细节，需要注意，建议先看视频。 

题目链接/文章讲解/视频讲解：代码随想录

重点：

1. 双指针法

思路：

1. 双指针法

(1) 先把数组从小到大排序

(2) 两个for循环，第一个for循环 i 从头开始，第二个for循环从上一个循环 i + 1 开始

(3) 不断的移动left和right，当i + j + left + right小于0时说明sum太小了，需要变大，因为是排序好的数组，直接把left++就可以把left移动到更大的数去了

(4) 不断的移动left和right，当i + j + left + right大于0时说明sum太大了，需要变小，因为是排序好的数组，直接把right--就可以把right移动到更小的数去了

(5) 当i + j + left + right等于0时，把这四个值存放到result中，接下来要对left和right分别去重。如果left = left + 1， left++。如果right = right - 1，right--

(6) 把 j 移动到下一个，接着判断

public static List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> result = new ArrayList<>();// 先从小到大排序数组Arrays.sort(nums);for (int i = 0; i < nums.length - 1; i++) {// 如果nums[i]已经大于target了，并且nums[i]已经大于0// nums[i]已经大于0说明后面的数肯定也都大于0，直接返回if (nums[i] > target && nums[i] > 0) {return result;}// 如果当前nums[i]和前一个数一样，跳过if (i >= 1 && nums[i] == nums[i - 1]) {continue;}for (int j = i + 1; j < nums.length; j++) {// 如果i和j已经相差两个，并且nums[j]和前一个数一样，跳过if (j > i + 1 && nums[j] == nums[j - 1]) {continue;}// 两个指针，一个指j + 1，一个指数组末尾int left = j + 1;int right = nums.length - 1;while (left < right) {long sum = (long)nums[i] + nums[j] + nums[left] + nums[right];if (sum > target) {// 当四数之和大于target时，证明需要减小，把right往前移一个right--;} else if (sum < target) {// 当四数之和小于target时，证明需要变大，把left往后移一个left++;} else {// 当四数之和等于target时，需要对left和right所指的数分别去重result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));while (left < right && nums[left + 1] == nums[left]) {left++;}while (left < right && nums[right - 1] == nums[right]) {right--;}left++;right--;}}}}return result;
}