Leetcode454四数之和思路参考我们之前做过的两数之和四数之和为 0 可以等价转换为nums1[i] nums2[j] -(nums3[k] nums4[l])基于这个等式我们可以把问题拆成两步第一步计算nums1和nums2所有两两组合的和用哈希表统计每个和出现的次数键 和值 次数。第二步计算nums3和nums4所有两两组合的和对每个和sum找哈希表中-sum对应的次数累加这个次数就是答案。问题为什么两数之和可以用数组存这个就要用map维度两数之和LeetCode 1四数相加 IILeetCode 454核心需求判断 “目标值 - 当前数” 是否存在统计 “两数之和” 出现的次数数值范围若范围可控可用数组否则用 Map范围不可控int 相加只能用 Map存储目标存 “数值→索引”单次映射存 “和→次数”计数映射内存效率范围可控时数组更高Map 更高稀疏存储不可控的范围就用map代码class Solution { public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { MapInteger, Integer sumMap new HashMap(); int count 0; // 计算nums1和nums2所有元素两两之和统计出现次数 for (int num1 : nums1) { for (int num2 : nums2) { int sum num1 num2; if (sumMap.containsKey(sum)) { // 存在取出原值 1 后重新存入 int currentCount sumMap.get(sum); sumMap.put(sum, currentCount 1); } else { // 不存在存入键值对值为1第一次出现 sumMap.put(sum, 1); } } } // 计算nums3和nums4所有元素两两之和累加符合条件的组合数 for (int num3 : nums3) { for (int num4 : nums4) { int sum num3 num4; int target -sum; if (sumMap.containsKey(target)) { // 存在则累加对应的值 count sumMap.get(target); } // 不存在则不处理等价于加0 } } return count; } }存在vuale1不存在存入的部分代码可优化存在则累加对应的值也可优化。sumMap.put(sum, sumMap.getOrDefault(sum, 0) 1); count sumMap.getOrDefault(target, 0);Java中不同数据类型获取长度的规则数据类型获取长度的方式类型属性 / 方法示例代码数组int []、String []length成员属性int[] arr {1,2,3}; System.out.println(arr.length); // 输出 3字符串Stringlength()成员方法String str hello; System.out.println(str.length()); // 输出 5集合List/Set/Mapsize()成员方法ListString list new ArrayList(); list.add(a); System.out.println(list.size()); // 输出 1注意Map 的特殊情况size()成员方法MapString, Integer map new HashMap(); map.put(age,18); System.out.println(map.size()); // 输出 1键值对数量map的增删查增 map.putIfAbsent(apple, 3);键不存在则新增键存在则覆盖原值返回值新增返回 null覆盖返回旧值 查 Integer v1 map.get(apple);根据键取值 Integer v3 map.getOrDefault(banana, 0);根据键取值键不存在返回默认值 boolean hasApple map.containsKey(apple);判断键是否存在 boolean has2 map.containsValue(2);判断值是否存在 删 Integer removed map.remove(apple); 根据键删除键值对返回值删除成功返回被删值失败返回null boolean removedOrange map.remove(orange, 4); 仅当键值完全匹配时删除返回值成功true失败falsePython实现python的实现比较简单用字典就行def fourSumCount(nums1, nums2, nums3, nums4): # 第一步统计 nums1 nums2 所有和的出现次数用字典模拟哈希表 sum_ab {} for a in nums1: for b in nums2: s a b # 统计次数存在则1不存在则设为1 sum_ab[s] sum_ab.get(s, 0) 1 # 第二步遍历 nums3 nums4 的和找相反数的次数并累加 count 0 for c in nums3: for d in nums4: s c d # 找 -s 在 sum_ab 中的次数不存在则加0 count sum_ab.get(-s, 0) return countget()是字典最常用的方法之一核心作用是根据键取值且能指定键不存在时的默认值避免 KeyError 报错。Leetcode383赎金信和前面做过的字母异味符很像只需要变一下最后的判断条件维度LeetCode 242有效的字母异位词LeetCode 383赎金信核心需求判断两个字符串的字符组成完全一致字符种类、每个字符的出现次数都相同顺序无关。例listen和silent返回true本质是 “双向相等”。判断一个字符串ransomNote的所有字符是否都能从另一个字符串magazine中获取每个字符的使用次数不超过 magazine 中的次数。例ransomNoteaa、magazineab返回false本质是 “单向包含”。解题思路核心是 “验证相等”1. 统计字符串 s 的字符频率 → 统计字符串 t 的字符频率 → 对比两个频率是否完全一致2. 也可排序后直接比较字符串是否相等。核心是 “验证包含”1. 先统计 magazine 的字符频率2. 遍历 ransomNote 的每个字符每用一个就将对应频率 - 13. 若任意字符频率 0 或不存在返回false否则返回true。class Solution { public boolean canConstruct(String ransomNote, String magazine) { // shortcut if (ransomNote.length() magazine.length()) { return false; } // 定义一个哈希映射数组 int[] record new int[26]; // 遍历 for(char c : magazine.toCharArray()){ record[c - a] 1; } for(char c : ransomNote.toCharArray()){ record[c - a] - 1; } // 如果数组中存在负数说明ransomNote字符串中存在magazine中没有的字符 for(int i : record){ if(i 0){ return false; } } return true; } }class Solution: def canConstruct(self, ransomNote: str, magazine: str) - bool: # 初始化26个字母的计数数组对应a-z char_count [0] * 26 # 第一步统计magazine中每个字符的出现次数充值 for c in magazine: char_count[ord(c) - ord(a)] 1 # 第二步扣除ransomNote需要的字符消费 for c in ransomNote: idx ord(c) - ord(a) char_count[idx] - 1 # 提前终止如果扣完后为负说明该字符不足直接返回False if char_count[idx] 0: return False # 所有字符扣除后都非负说明满足条件 return TrueLeetcode15三数之和三个数降一维固定一个数在剩下的数组里找两个数使得nums[left] nums[right] -nums[i]这就变成了经典的两数之和其他思考问题如果数组是无序的可以用哈希表但是这题还有额外的要求结果不能重复这就提醒我们要有一个关键的操作是排序。排序的优势排序后数组是递增的可以方便又双指针相同的数字会挨在一起可以快速去重。class Solution: def threeSum(self, nums: List[int]) - List[List[int]]: nums.sort() res [] n len(nums) for i in range(n - 2): # 跳过重复的第一个数 if i 0 and nums[i] nums[i - 1]: continue left, right i 1, n - 1 while left right: total nums[i] nums[left] nums[right] if total 0: res.append([nums[i], nums[left], nums[right]]) # 去重跳过相同的左值 while left right and nums[left] nums[left 1]: left 1 # 去重跳过相同的右值 while left right and nums[right] nums[right - 1]: right - 1 left 1 right - 1 elif total 0: left 1 else: right - 1 return res为什么去重要放到找到一个答案之后去重必须放在「找到一个合法三元组之后」因为只有在确定当前组合已经被记录后才能安全地跳过所有与它等价的重复值。如果提前去重可能会跳过本来应该被计算的组合。java代码细节在list里面放list