Leecode刷题 Day7----------哈希表

Leecode刷题 Day7----------哈希表

1. 四数相加II（454）

• 题目链接：https://leetcode.cn/problems/4sum-ii/
• 文章讲解/视频讲解：https://programmercarl.com/0454.%E5%9B%9B%E6%95%B0%E7%9B%B8%E5%8A%A0II.html

重点：

• 不用去重，两组0000，0000分别来自四个数组，但是每个0来自一个数组的不同位置。这样算两组，无需去重。
• 重点在于Map的key是分别第一个数组和分别第二个数组的和，value是这个和出现的次数！ 类似于两数之和！
• count+=map.get(0-temp); 意味着这么多组不去重！

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer, Integer> map=new HashMap<>();
        int count=0;
        for(int i:nums1){
            for(int j:nums2){
                int temp=i+j;
                if(map.containsKey(temp)) map.put(temp,map.get(temp)+1);
                else map.put(temp,1);
            }
        }
        for(int i:nums3){
            for(int j:nums4){
                int temp=i+j;
                if(map.containsKey(0-temp)) count+=map.get(0-temp);
            }
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2. 赎金信 （383）

• 题目链接：https://leetcode.cn/problems/ransom-note/
• 文章讲解：https://programmercarl.com/0383.%E8%B5%8E%E9%87%91%E4%BF%A1.html

重点：与字母异位很类似！！！！只要有<0，就是false

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] ints=new int[26];
        
        for(int i=0;i<magazine.length();i++){
            ints[magazine.charAt(i)-'a']++;
        }
        for(int i=0;i<ransomNote.length();i++){
            ints[ransomNote.charAt(i)-'a']--;
        }
        for(int i=0;i<ints.length;i++){
            if(ints[i]<0) return false;
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3. 三数之和 （15）

• 题目链接：https://leetcode.cn/problems/3sum/
• 文章讲解/视频讲解：https://programmercarl.com/0015.%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C.html

重点：

1. 题意表明要去重！！！000可以的，如果有两组000是不行的（因为原数组里可能有重复的0，四个0等）
2. 三个数字的去重方式不同：
   2.1 第一个数字是在开始的时候就去重，如果这个和左边已经加过的数字相同时跳过-------if(i>0&&nums[i]==nums[i-1]) continue;
   2.2 第二个数字left是如果下一个和这个相同时就直接给指针+±-------while(right > left&&nums[left]==nums[left+1]) left++;
   2.3 第三个数字right是如果下一个和这个相同时就直接给指针–,---------------- while(right > left&&nums[right]==nums[right-1]) right–;
3. left = i+1
4. 判断sum 与0的关系从而控制 left 和 right 指针的移动方向
5. 注意数组不要越界，只要看到数组索引+1或-1就要敏感-----判断：i的大小&&条件
6. 库函数：list.add(Arrays.asList(nums[i], nums[left], nums[right]));

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list=new ArrayList<>();
        Arrays.sort(nums);
        for(int i=0;i<nums.length;i++){
            if(nums[i]>0) return list;
            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{
                    list.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    while(left+1<nums.length && nums[left]==nums[left+1]) left++;
                    while(right>1 & &nums[right]==nums[right-1]) right--;
                    left++;
                    right--;
                }    
            }
        }
        return list;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

4. 四数之和 （18）

• 题目链接：https://leetcode.cn/problems/4sum/
• 文章讲解/视频讲解：https://programmercarl.com/0018.%E5%9B%9B%E6%95%B0%E4%B9%8B%E5%92%8C.html

与上题的不同点：

1. 加一层for循环，j=i+1
2. j 的判断条件：是否>i+1 && 条件
3. 不知道target与0的关系，如果该数>target并且该数为正数，这是不存在的
   if(nums[i]>0 && nums[i]>target) return list;

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> list=new ArrayList<>();
        Arrays.sort(nums);
        for(int i=0;i<nums.length;i++){
            //如果该数>target并且该数为正数，这是不存在的
            if(nums[i]>0 && nums[i]>target) return list;
            if(i>0&&nums[i]==nums[i-1]) continue;
            
            for(int j=i+1;j<nums.length;j++){
                if(j>i+1 && nums[j]==nums[j-1]) continue;
                int left=j+1;
                int right=nums.length-1;
                while(left<right){
                    int sum=nums[i]+nums[j]+nums[left]+nums[right];
                    if(sum>target) right--;
                    else if(sum<target) left++;
                    else{
                        list.add(Arrays.asList(nums[i], nums[j],nums[left], nums[right]));
                        while(left+1<nums.length&&nums[left]==nums[left+1]) left++;
                        while(right>1&&nums[right]==nums[right-1]) right--;
                        left++;
                        right--;
                    }    
                }
            }
            
        }
        return list;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

5. 总结

454. 四数相加 与 18. 四数之和，15. 三数之和 的区别：

454 为四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑重复问题
18. 四数之和 ，15.三数之和 是一个数组（集合）里找到和为0的组合，难很多！