LeeCode哈希问题(二)
2022/7/4 6:21:58
本文主要是介绍LeeCode哈希问题(二),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
LeeCode 454: 四数相加II
题目描述
给你四个整数数组
nums1
、nums2
、nums3
和nums4
,数组长度均为n
,请你计算有多少个元组 (i, j, k, l) 能满足:
- \(0 \le i, j, k, l < n\)
- \(nums[i] + nums[j] + nums[k] + nums[l] == 0\)
标签:数组,哈希
时间复杂度:\(O(N^2)\)
建立模型
- 使用一个哈希表保存
nums1
和nums2
出现的两数之和以及次数 - 计算
nums3
和nums4
的两数之和,并在哈希表中寻找nums3
和nums4
和的相反数 - 统计步骤二中找到的次数
代码实现
# Python3 实现 def solution(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int: dict = {} for i in nums1: for j in nums2: dict[i + j] = dict.get(i + j, 0) + 1 res = 0 for k in nums3: for l in nums4: if -(k + l) in dict: res += dict.get(-(k + l)) return res
// Java 实现 public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { Map<Integer, Integer> map = new HashMap<>(); for (int i : nums1) { for (int j : nums2) { map.put(i + j, map.getOrDefault(i + j, 0) + 1); } } int res = 0; for (int k : nums3) { for (int l : nums4) { if (map.containsKey(-(k + l))) { res += map.get(-(k + l)); } } } return res; }
LeeCode 383: 赎金信
题目描述
给你两个字符串:
ransomNote
和magazine
,判断ransomNote
能不能由magazine
里面的字符构成。如果可以则返回
true
,否则返回false
。magazine
中的每个字符只能在ransomNote
中使用一次。
标签:字符串,哈希
时间复杂度:O(N)
建立模型
- 遍历
magezine
统计出现的字符及次数,并保存在哈希表中 - 遍历
ransonNote
字符串,每个字符出现一次,则将哈希表中对应次数减1 - 若哈希表出现某个字符数小于0,则说明不能由
magazine
构成,返回false
- 若遍历完成未出现步骤3的情况,则返回
true
代码实现
# Python3 实现 def canConstruct(self, ransomNote: str, magazine: str) -> bool: dict = {} for ch in magazine: dict[ch] = dict.get(ch, 0) + 1 for ch in ransomNote: dict[ch] = dict.get(ch, 0) - 1 if dict[ch] < 0: return False return True
// Java 实现 public boolean canConstruct(String ransomNote, String magazine) { Map<Character, Integer> map = new HashMap<>(); for (char ch : magazine.toCharArray()) { map.put(ch, map.getOrDefault(ch, 0) + 1); } for (char ch : ransomNote.toCharArray()) { map.put(ch, map.getOrDefault(ch, 0) - 1); if (map.get(ch) < 0) { return false; } } return true; }
LeeCode 15: 三数之和
题目描述
给你一个包含
n
个整数的数组nums
,判断nums
中是否存在三个元素 a, b, c, 使得 \(a + b + c = 0\)?请你找出所有和为 0 且不重复的三元组。
标签:数组,双指针,排序
时间复杂度:\(O(N^2)\)
建立模型
- 对 nums 数组做升序重排
- 如果数组的长度小于3 或 重排后第一个数大于0,则直接返回空数组
- 循环遍历数组中的元素(index),使其为3元组的第1个数
- 则第2个数(left)设为 index + 1,第3个数(right)设为 len(nums) - 1
- 若 \(index + left + right < 0 \Rightarrow left += 1\)
- 若 \(index + left + rigght > 0 \Rightarrow right -= 1\)
- 若 \(index + left + right == 0 \Rightarrow\) 该3元组为其中一个解
如何去除重复三元组
- 对于三元组的第一个数,\(nums[index] == nums[index - 1] \rightarrow continue\)
- 对于三元组的第二个数,\(nums[left] == nums[left + 1] \rightarrow left += 1\)
- 对于三元组的第三个数,\(nums[right] == nums[right - 1] \rightarrow right -= 1\)
代码实现
# Python3 实现 def threeSum(self, nums: List[int]) -> List[List[int]]: res = [] nums.sort() if len(nums) < 3 or nums[0] > 0: return res for index in range(len(nums)): if index > 0 and nums[index] == nums[index - 1]: continue temp, left, right = nums[temp], index + 1, len(nums) - 1 if temp + nums[left] + nums[right] < 0: left += 1 elif temp + nums[left] + nums[right] > 0: right -= 1 else: res.append([temp, nums[left], nums[right]]) while left < right and nums[left] == nums[left + 1]: ledt += 1 while left < right and nums[right] == nums[right - 1]: right -= 1 left += 1 right -= 1 return res
// Java 实现 public List[List[Integer]] threeSum(int[] nums) { Arrays.sort(nums); if (nums.length < 3 || nums[0] > 0) { return new ArrayList<>(); } List<List<Integer>> res = new ArrayList<>(); for (int i = 0; i < nums.length; i++) { if (i > 0 && nums[i] == nums[i - 1]) continue; int temp = nums[i]; int left = i + 1, right = nums.length - 1; while (left < right) { if (temp + nums[left] + nums[right] < 0) { left += 1; } else if (temp + nums[left] + nums[right] > 0) { right -= 1; } else { List<Integer> list = new ArrayList<>(); list.add(temp); list.add(nums[left]); list.add(nums[right]); res.add(new ArrayList<>(list)); while (left < right && nums[left] == nums[left + 1]) left += 1; while (left < right && nums[right] == nums[right - 1]) right -= 1; left += 1; right -= 1; } } } return res; }
LeeCode 18: 四数之和
题目描述
给你一个由
n
个整数组成的数组nums
,和一个目标值target
。请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]]
:
- \(0 \le a, b, c, d < n\)
- \(a, b, c, d\)互不相同
- \(nums[a] + nums[b] + nums[c] + nums[d] == target\)
核心思想:该题的思路和三数之和完全一致,只是在外面多嵌套一层循环,所有时间复杂度是\(O(N^3)\)
代码实现
# Python3 实现 def solution(self, nums: List[int], target: int) -> List[List[int]]: res = [] if len(nums) < 4: return res nums.sort() for i in range(len(nums)): if i > 0 and nums[i] == nums[i - 1]: continue if 4 * nums[i] > target: continue for j in range(i + 1, len(nums)): if j > i + 1 and nums[j] == nums[j - 1]: continue if nums[i] + 3 * nums[j] > target: break left, right = j + 1, len(nums) - 1 while left < right: if nums[i] + nums[j] + nums[left] + nums[right] < target: left += 1 elif nums[i] + nums[j] + nums[left] + nums[right] > target: right -= 1 else: res.append([nums[i], nums[j], 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, right = left + 1, right - 1 return res
这篇关于LeeCode哈希问题(二)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升