刷题LeetCode 第六天

LeetCode 454

1. 看到题目的第一想法
   看到题目的第一想法就是先算前两个数，然后再求后两个数的相反数就是等于前两个数，是不是包含。一开始的想法是使用set来做，但是没有考虑到还要保存出现的次数。为什么？

2. 看完题解后的想法
   比如下面的例子，要考虑使用

nums1[1]+nums2[2]=5
nums1[2]+nums2[3]=5
nums1[3]+nums2[4]=5
那么这里5就出现了三次
如果后面
nums3[1]+nums4[2]=-5
那么这个组合可以和前面三个都能进行组合，都是符合要求的。
所以对于前面两个数，求和之后一定要记录次数

通过上面的例子那么就要使用map来保存。
看完题解后，就是使用map来保存

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int result=0;
        int count=0;
        Map<Integer,Integer> map1= new HashMap<>();
        for(int i=0;i<nums1.length;i++){
            for(int j=0;j<nums2.length;j++){
                int temp = nums1[i]+nums2[j];
                if(map1.containsKey(temp)){//计算前两个数的和然后看在map1里面嘛，在的话找到那个数，并给对应的次数+1
                    map1.put(temp,map1.get(temp)+1);
                }else{//不在的话，就给对应的次数赋1
                    map1.put(temp,1);
                }
            }
        }
        for(int i=0;i<nums3.length;i++){
            for(int j=0;j<nums4.length;j++){
                int target=(0-(nums3[i]+nums4[j]));
                if(map1.containsKey(target)){//是否在map中在的话，求对应的次数然后相加
                    result+=map1.get(target);
                }
            }
        }
        return result;
    }
}

3. 遇到的困难
   这里对于Map的添加，查询使用的函数不是很明确
   添加put，查询containsKey

LeetCode 383

1. 看到题目的第一想法
   使用哈希的额方法，在一个字符串中找另一个字符串是否存在。刚开始是使用set的方式，但是不行。重要欠缺在方法使用上，哈希对应的函数不熟悉。
2. 看完题解后的想法
   和之前判断两个字符串总，是否可以由一个字符串组成另一个字符串的方法类似，都是使用数组。

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

3. 遇到的困难
   遇到看一个字符串中是否在有另一个字符串中的元素存在，首要考虑使用数组的方式，一个++，一个–，然后判断最后是否为0。

LeetCode 15

1. 看到题目的第一想法
   就是想用之前的方法，先计算前两个数之和，然后对第三个数求相反数看是否等于前两个，如果等于就是一组。但是没有考虑到去重的事，题目要求是可以重用里面的内部元素，但是不能是同一个数。
   所以最关键的逻辑在于去重

2. 看完题解后的想法
   使用双指针法，进行判断。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> temp=new ArrayList<>();
        Arrays.sort(nums);//先排序
        for(int i=0;i<nums.length;i++){
            if(i>0 && nums[i]==nums[i-1]){必须是比较和前一个元素，因为实际存储的是i,left,right这样的结构
                continue;
            }
            if(nums[i]>0) return result;//如果第一个元素都大于0，那么久直接返回
            
                int left=i+1;
                int right=nums.length-1;
                while(left<right){
                    if(nums[i]+nums[left]+nums[right]>0){
                        right--;
                    }else if(nums[i]+nums[left]+nums[right]<0){
                        left++;
                    }else{
                        result.add(Arrays.asList(nums[i],nums[left],nums[right]));
                        while(left<right && nums[left]==nums[left+1]) left++;
                        while(left<right && nums[right]==nums[right-1]) right--;
                        //出现-1，-1，-1,0,1，1,1这种情况的，要去重
                        left++;
                        right--;
                    }
                    
                }

            }
        
        return result;
    }
}

3. 遇到的困难
   去重逻辑很难想到

LeetCode 18

1. 看到题目的第一想法
   使用三数之和的逻辑，把前两个数看成一个整体，然后看第三个数和最后一个数都是left，right，但是不清楚前两个数如何去重。
2. 看完题解后的想法
   前两个数对应三数之和最外层的数，先做剪枝和去重，然后到内部继续剪枝和去重

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for(int i=0;i<nums.length;i++){
            if(i>0 && nums[i]==nums[i-1]){
                continue;
            }
            if(nums[i]>target && nums[i]>=0) break;
            for(int j=i+1;j<nums.length;j++){
                if(j>i+1 && nums[j]==nums[j-1]){
                    continue;
                }
                if(nums[i]+nums[j]>target && nums[i]+nums[j]>=0) break;
                int left=j+1;
                int right=nums.length-1;
                while(left<right){
                    if(nums[i]+nums[j]+nums[left]+nums[right]>target){
                        right--;
                    }else if(nums[i]+nums[j]+nums[left]+nums[right]<target){
                        left++;
                    }else{
                        result.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                        while(left<right && nums[right]==nums[right-1]) right--;
                        while(left<right && nums[left]==nums[left+1]) left++;
                        left++;
                        right--;
                    }
                }
            }
        }
        return result;
    }
}

3. 遇到的困难
   对于三数之和的思路没有完全理解。对于target可能是一个小于0 的数，所以
   比如-4 -1 0 0，target=-5，那么我们不能按照三数之和那样判断如果第一个数大于target的话就进入下一个循环，所以判断条件应该修改。target>0且nums[i]>0那么久可以采用上面的方式。

总结

对于hash函数类的题目，首要就是读懂题意，如果是判断一个数是否在另一个数中存在，那么就要考虑到使用hash函数，此外数组也可以理解为一种特殊的hash函数。在解题的过程中，比如三数之和，四数之和要考虑到使用双指针进行求解。