day07补卡|哈希表专题02|Leetcode454、383、15、18|四数之和、三数之和、赎金信、四数相加II

Leetcode454:四数相加II

题���链接：https://leetcode.cn/problems/4sum-ii/description/

题目分析：使用哈希map

ABCD四个数组 ；map1: A+B ; 查询0-(c+d)是否在map1内出现；O（n^2）

key:和(a+b;c+d) value 出现次数

如果对应c+d 能找到对应的map1的值；它的count应该加对应的value值

Java代码：

class Solution {    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {        int count = 0;        HashMap map12sum = new HashMap();        for (int n1 : nums1) {            for (int n2 : nums2) {                int sum = n1+n2;                if(map12sum.containsKey(sum)){                    map12sum.put(sum,map12sum.get(sum)+1);                }else {                    map12sum.put(sum,1);                }            }        }        HashMap mapCD = new HashMap();        for (int n3 : nums3) {            for (int n4 : nums4) {                //也可以用map.getOrDefault()                if (map12sum.containsKey(-n3-n4)){                    count += map12sum.get(-n3-n4);                }            }        }        return count;            }}

Leetcode383:赎金信

题目链接：https://leetcode.cn/problems/ransom-note/description/

题目解析：原理和:有效的字母异位词相似，依旧是哈希数组实现

magzine字符串遍历字符，出现对应位置+1；ransomNote遍历字符，对应位置-1，同时判断更改位置字符value是否为负，如遇到负，直接false;

还有无序判断具体字符就可以得到答案的情况：

1.magzine magazine.length()) { return false; } int[] record = new int[26]; for(int i = 0;i0,所以不会存在和为0的情况

class Solution {    public List fourSum(int[] nums, int target) {        List result = new ArrayList();        if(nums.length  target && (nums[k] >=0 || target >= 0)            if(nums[k]>target && (nums[k] >=0 || target >= 0)){                break;            }            if(k>0 && nums[k] == nums[k-1]){                continue;            }            for(int i = k+1;itarget && nums[i]>=0){                    break;                }                //这里i>0 -> i>k+1(初始值)                if(i>k+1 && nums[i] == nums[i-1]){                    continue;                }                int left = i+1;                int right = nums.length-1;                while(lefttarget){                        right--;                    }else if(sum