54. 四数相加 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.两数之和 解法类似；区别在于两数组元素之和作为key，两数组元素之和相同的次数作为value

class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int res = 0;// 两数组元素之和作为Key，两数组元素之和相同的次数作为valueMap map = new HashMap<>();for (int i : nums1) {for (int j : nums2) {int sum = i + j;if (map.containsKey(sum)) {map.put(sum, map.get(sum) + 1);} else {map.put(sum, 1);}}}//统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数for (int i : nums3) {for (int j : nums4) {int sum = i + j;if (map.containsKey(0 - sum)) {res += map.get(0 - sum);}}}return res;}
}

383. 赎金信

[题目链接](383. 赎金信 - 力扣（Leetcode）)

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

解法：定义数组 record[] 当作哈希表使，数组长度为26，对应26个英文小写字母；然后遍历magazine字符串，通过表达式： 字符 - ‘a’ 计算出字符存放的位置，但不存字符值，而是进行+1操作，比如字符串中 ‘c’ 出现了5次，则record[‘c’ - ‘a’] 的值为5; magazine字符串遍历结束后开始遍历ransomNote字符串，和magazine字符的遍历逻辑类似，区别在于这次采取-1操作，如果有位置小于0，则不满足条件；、、

class Solution {public boolean canConstruct(String ransomNote, String magazine) {if (ransomNote.length() > magazine.length()) {return false;}int[] records = new int[26];for (char i : magazine.toCharArray()) {records[i - 'a']++;}for (char j : ransomNote.toCharArray()) {records[j - 'a']--;if (records[j - 'a'] < 0) {return false;}}return true;}
}

15. 三数之和

[题目链接](15. 三数之和 - 力扣（Leetcode）)

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

解法：排序 + 双指针； 其中三元组的去重直接用HashSet存放数据就可；[视频讲解](梦破碎的地方！| LeetCode：15.三数之和_哔哩哔哩_bilibili)

**注意：**答案中不可以包含重复的三元组。

class Solution {public List> threeSum(int[] nums) {Arrays.sort(nums);Set> resultSet = new HashSet<>();for (int i = 0; i < nums.length; i++) {if (nums[i] > 0) {return new ArrayList>(resultSet);}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 {List threeSum = new ArrayList<>();threeSum.add(nums[i]);threeSum.add(nums[left]);threeSum.add(nums[right]);resultSet.add(threeSum);left++;right--;}}}return new ArrayList>(resultSet);}
}

18. 四数之和

[题目链接](18. 四数之和 - 力扣（Leetcode）)

解法和 [15.三数之和](15. 三数之和 - 力扣（Leetcode）) 类似，多一层for循环

class Solution {public List> fourSum(int[] nums, int target) {Arrays.sort(nums);Set> resultSet = new HashSet<>();for (int i = 0; i < nums.length; i++) {for (int j = i + 1; j < nums.length; j++) {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) {right--;} else if (sum < target) {left++;} else {List fourSum = new ArrayList<>();fourSum.add(nums[i]);fourSum.add(nums[j]);fourSum.add(nums[left]);fourSum.add(nums[right]);resultSet.add(fourSum);left++;right--;}}}}return new ArrayList>(resultSet);}
}