代码随想录算法训练营 Day7 | 哈希表 | 454.四数相加II 、383. 赎金信 、15. 三数之和、 18. 四数之和
补博客打卡。。。
454. 四数相加 II
两数之和哈希表的解法思路稍微改变一点点
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
HashMap<Integer,Integer> map = new HashMap<>();
int count = 0;
for(int num1 : nums1){
for(int num2 : nums2){
map.put(num1 + num2,map.getOrDefault(num1 + num2,0)+1);
}
}
for(int num3 : nums3){
for(int num4 : nums4){
int temp = 0 - (num3 + num4);
if(map.containsKey(temp)){
count += map.get(temp);
}
}
}
return count;
}
}
383. 赎金信
哈希表思路
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
HashMap<Character,Integer> map = new HashMap<>();
for(int i = 0; i < magazine.length(); i++){
map.put(magazine.charAt(i),map.getOrDefault(magazine.charAt(i),0)+1);
}
for(int i = 0; i < ransomNote.length(); i++){
if(!map.containsKey(ransomNote.charAt(i))) return false;
int cnt = map.get(ransomNote.charAt(i));
if(cnt < 1) return false;
if(cnt -1 <= 0){
map.remove(ransomNote.charAt(i));
}else{
map.put(ransomNote.charAt(i),cnt - 1);
}
}
return true;
}
}
15. 三数之和
本题用哈希法写也可以，但是很麻烦，用双指针思路
1. 先将数组从小到大排序
2. for循环遍历数组，然后设置两个指针left，right
3. 将三数之和与0比较，如果大于0，则right–，小于0则left++
4. 注意事项：
- 需要返回不重复的元组，需要去重
- 可以适当剪枝，减少没有意义的循环，如果第一个元素（排序后前面元素比后面元素小）就已经大于0，则后面相加肯定也会大于0，已经凑不齐相加等于0的元组了，则可以直接跳过。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
for(int i = 0; i < nums.length; i++){
//剪枝，如果最小的数都大于0了，则后面的数相加必然也会大于0，肯定凑不出相加为0的三元组了。
if(nums[i] > 0) return res;
//负责nums[i]的去重，如果nums[i]的数出现过一次了，说明之前已经用nums[i]当第一个数，然后遍历left，right双指针扫过一遍了。
if(i > 0 && nums[i] == nums[i-1]) continue;
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{
res.add(Arrays.asList(nums[i],nums[left],nums[right]));
//负责nums[j],nums[k]的去重
while(left < right && nums[left] == nums[left + 1]) left++;
while(left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
}
}
}
return res;
}
}
18. 四数之和
本题跟 454. 四数相加 II 不同的是，本题需要考虑去重，所以用哈希表不太好处理
用三数之和的思路再加点修改，在一次for循环遍历加双指针遍历的基础上再加一层for循环
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> res = new ArrayList<>();
int len = nums.length;
Arrays.sort(nums);
for(int k = 0; k < len; k++){
//剪枝,如果是正数，且最小的数都已经大于target了，说明已经凑不出四元组了
if(target > 0 && nums[k] > 0 && nums[k] > target) return res;
//对a去重
if(k > 0 && nums[k] == nums[k - 1]) continue;
for(int i = k + 1; i < len; i++){
//对b去重
if(i > k + 1 && nums[i] == nums[i -1]) continue; // 这里注意应该是i > k + 1 而不是下意识的写成i > 0
int left = i + 1;
int right = len - 1;
while(left < right){
//防止溢出
long sum = (long)nums[k] + nums[i] + nums[left] + nums[right];
if(sum > target){
right--;
}else if(sum < target){
left++;
}else{
//收集结果
res.add(Arrays.asList(nums[k],nums[i],nums[left],nums[right]));
//去重,将与本次结果一样的重复的数字去掉
while(left < right && nums[left] == nums[left + 1]) left++;
while(left < right && nums[right] == nums[right - 1]) right--;
//收集完结果，两指针同时向中间缩进
right--;
left++;
}
}
}
}
return res;
}
}