哈希表part02-代码随想录第7天
2023-12-20 07:11:04
哈希表part02-代码随想录第7天
今日任务
● 454.四数相加II
● 383. 赎金信
● 15. 三数之和
● 18. 四数之和
● 总结
1. 454.四数相加II
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
//用哈希法
//先遍历前两个数组元素得和,存到哈希表中,并统计相加一样结果出现得频率
//再遍历后面两个数组的和,用0去减去后面两个数组元素的和得到目标值
//然后如果得到的话,就证明找到一对四个相加为0的元组
//那么就返回目标值在哈希表中存储的频率value
//如果没有找到,就返回0
//要存储元素值,和下标,用map
Map<Integer,Integer> hashmap1=new HashMap<>();
for (int num1:nums1){
for(int num2:nums2){
//1-1,2 2-1,2
//统计加起来的值
int sum=num1+num2;
//存进HashMap中(ket,value) (sum,出现的频率)
hashmap1.put(sum,hashmap1.getOrDefault(sum, 0) + 1);
//hashmap1[num1+num2]++;
}
}
int count=0;
for(int num3:nums3){
for(int num4:nums4){
int target=0-(num3+num4);
// if(hashmap1[num3+num4]==target){
// //证明有元组
// count+=hashmap1.get(target);
// }
count+=hashmap1.getOrDefault(0-num3-num4,0);
}
}
return count;
}
}
2. 383. 赎金信
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
//判断一个字符串元素能不能由另外一个字符串构成
//将第一个字符串遍历(在二中得全部被包含),记录出现的频率
int[] arr=new int[26];//因为只有26个小写字母
for(int i=0;i<ransomNote.length();i++){
arr[ransomNote.charAt(i)-'a']++;
}
for(int i=0;i<magazine.length();i++){
arr[magazine.charAt(i)-'a']--;
}
for(int num:arr){
if(num>0){
//那么就是没有
return false;
}
}
//全部遍历完
return true;
}
}
3.15. 三数之和
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
//用三指针法
//先将整个数组进行排序
//第一个指针,由数组第一个元素开始
//如果第一个指针>0,后面的指针也就没必要进行下去了,因为此时是排序后的数组,最小的都大于0了,那么也就不存在三元数组
//第二个指针,是在第一个指针上+1位置上
//第三个指针,是数组的最后一个元素,也就是nums.length-1
//第二个指针加上第一个指针再加上第三个指针,如果值还是<0时,就将第二个指针往后移动一位
//如果>0,证明三个数太大了,第一位指针又是固定的,那么我们就将最后一个指针往前移动一位,让它减小
//先将数组进行排序
Arrays.sort(nums);
//定义一个二维集合
List<List<Integer>> result=new ArrayList<>();
//定义其他两个指针
for(int i=0;i<nums.length;i++){
//如果第一个指针>0,后面的指针也就没必要进行下去了,因为此时是排序后的数组,最小的都大于0了,那么也就不存在三元数组
if(nums[i]>0){return result;}
//进行去重
if(i>0&&nums[i]==nums[i-1]){
continue;//直接跳到下一层循环
}
//初始化left和right的值
int left=i+1;
int right=nums.length-1;
//进行指针的移动和输出成功的元组
//条件为left<right,不能为相等,因为两个在同一个地方,三个指针就变成了两个指针,也就不成三元组了
while (left<right){
if(nums[i]+nums[left]+nums[right]>0){
right--;
}else if(nums[i]+nums[left]+nums[right]<0){
left++;
}else{
//也就是nums[i]+nums[left]+nums[right]=0的时候
//往二位集合去存一组成功的元组
result.add(Arrays.asList(nums[i],nums[left],nums[right]));
//对第二个数和第三个数进行去重,也就是left和right
while(left<right&&nums[right]==nums[right-1]){
//right指针的值如果和前一位相等的话,就去重
right--;
}
while(left<right&&nums[left]==nums[left+1]){
//left指针的值如果和后一位相等的话,就去重
left++;
}
//让right和left一直往中间移动
//
right--;
left++;
}
}
}
return result;
}
}
4. 18. 四数之和
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
//在三数之和的基础上多增加一层for循环,然后改变i的那层(进行剪枝)
//先将数组进行排序
Arrays.sort(nums);
//定义一个二维集合
List<List<Integer>> result=new ArrayList<>();
//定义其他两个指针
for(int k=0;k<nums.length;k++){
if(nums[k]>0&&nums[k]>target){
//当target为正数时,元素第一个值如果大于target(排序之后的数组第一个元素)
//后面也就不用看了
return result;
}
//对nums[k]进行去重
if(k>0&&nums[k-1]==nums[k]){
//第一个下标不能算了,得从第二个开始(第一个就去重没意义)
continue;
}
//第二层
for(int i=k+1;i<nums.length;i++){
//对nums[i]进行去重
if(i>k+1&&nums[i-1]==nums[i]){
continue;//直接跳到下一层循环
}
//初始化left和right的值
int left=i+1;
int right=nums.length-1;
//进行指针的移动和输出成功的元组
//条件为left<right,不能为相等,因为两个在同一个地方,三个指针就变成了两个指针,也就不成三元组了
while(left<right){
if(nums[k]+nums[i]+nums[left]+nums[right]>target){
right--;
}else if(nums[k]+nums[i]+nums[left]+nums[right]<target){
left++;
}else{
//也就是nums[i]+nums[left]+nums[right]=0的时候
//往二位集合去存一组成功的元组
result.add(Arrays.asList(nums[k],nums[i],nums[left],nums[right]));
//对第二个数和第三个数进行去重,也就是left和right
while(left<right&&nums[right]==nums[right-1]){
//right指针的值如果和前一位相等的话,就去重
right--;
}
while(left<right&&nums[left]==nums[left+1]){
//left指针的值如果和后一位相等的话,就去重
left++;
}
//让right和left一直往中间移动
//
right--;
left++;
}
}
}
}
return result;
}
}
文章来源:https://blog.csdn.net/Belle_Daisy/article/details/135097599
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!