哈希表part02-代码随想录第7天

哈希表part02-代码随想录第7天

今日任务

● 454.四数相加II

● 383. 赎金信

● 15. 三数之和

● 18. 四数之和

● 总结

1. 454.四数相加II

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. 赎金信

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. 三数之和

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. 四数之和

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;
    }
}