网站建设 税点,南宁seo优势,wordpress输出自定义文章类型内容,贵州健康码app下载目录
454. 四数相加 II
383. 赎金信
15. 三数之和
18. 四数之和 454. 四数相加 II
难度#xff1a;medium
类型#xff1a;哈希表
思路#xff1a; 本题是使用哈希法的经典题目#xff0c;而0015.三数之和 (opens new window)#xff0c;0018.四数之和 (opens new …目录
454. 四数相加 II
383. 赎金信
15. 三数之和
18. 四数之和 454. 四数相加 II
难度medium
类型哈希表
思路 本题是使用哈希法的经典题目而0015.三数之和 (opens new window)0018.四数之和 (opens new window)并不合适使用哈希法因为三数之和和四数之和这两道题目使用哈希法在不超时的情况下做到对结果去重是很困难的很有多细节需要处理。 对于本题我们使用哈希法先将nums1和nums2遍历相加后的结果放进mapkey为数组对应的和value为该和出现的次数。然后再对nums3和nums4进行遍历相加去map中寻找其和的相反数若找到就累计其value存储的出现次数。
代码
class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {// key存放nums1和nums2中元素对应和value存放和出现的次数MapInteger, Integer map new HashMap();int len nums1.length;// 遍历nums1和nums2的元素和for (int i: nums1) {for (int j: nums2) {int sum i j;map.put(sum, map.getOrDefault(sum, 0) 1);}}// 统计满足条件的元组数量int ans 0;// 遍历nums3和nums4的元素和for (int i: nums3) {for (int j: nums4) {int sum i j;if (map.containsKey(-sum)) {ans map.get(-sum);}}}return ans;}
} 复杂度分析
时间复杂度 O(n^2)空间复杂度: O(n^2)最坏情况下A和B的值各不相同相加产生的数字个数为 n^2 383. 赎金信
难度easy
类型哈希表 思路 用数组做哈希表类似于242.有效的字母异位词但有略微的区别。用hash存储magazine每个字母出现的次数再遍历ransomNote元素出现的次数hash中若有元素小于0则说明不行
代码
class Solution {public boolean canConstruct(String ransomNote, String magazine) {int[] hash new int[26];for (int i 0; i magazine.length(); i) {hash[magazine.charAt(i) - a];}for (int i 0; i ransomNote.length(); i) {hash[ransomNote.charAt(i) - a]--;}for (int i: hash) {if (i 0) {return false;}}return true;}
}
复杂度分析
时间复杂度: O(n)空间复杂度: O(1) 15. 三数之和
难度medium
类型哈希表双指针 思路 因为要去重所以使用哈希法太复杂我们使用双指针法 i进行数组遍历在每个i中left和right分别从i1和数组末尾相向出发若nums[i] nums[left] nums[right] 0 则right--nums[i] nums[left] nums[right] 0 则left。 需要注意的去重 对i去重和后一个元素比较为什么不是判断nums[i] nums[i1]呢答考虑[0,0,0] 对right去重若right left nums[right] nums[right - 1]则right-- 对left去重同理 代码
class Solution {public ListListInteger threeSum(int[] nums) {// 二维列表存储结果ListListInteger ans new ArrayList();// 数组排序Arrays.sort(nums);// i遍历数组i为三元组的第一个数for (int i 0; i nums.length - 2; i) {// 剪枝如果最小的数大于0那么三元组的和不可能为0if (nums[i] 0) {break;}// 对i去重和后一个元素比较为什么不是判断nums[i] nums[i1]呢// 答考虑[0,0,0]特殊情况if (i 0 nums[i] nums[i - 1]) {continue;}int left i 1;int right nums.length - 1;// 开始移动left和rightwhile (left right) {int sum nums[i] nums[left] nums[right];// 符合条件存入结果列表if (sum 0) {ans.add(Arrays.asList(nums[i], nums[left], nums[right]));// 对right去重while (right left nums[right] nums[right - 1]) {right--;}// 对left去重while (right left nums[left] nums[left 1]) {left;}// 去重后还需要再移动一次才是新的元素right--;left;} else if (sum 0) {right--;} else if (sum 0) {left;}}}return ans;}
}
复杂度分析
时间复杂度: O(n^2)空间复杂度: O(1) 18. 四数之和
难度medium
类型哈希表双指针 思路
卡哥的四数之和解析写得很好 这道题是三数之和的扩展板外面再套一层for就可以五数之和、六数之和同理 注意 外面两层for都要进行去重; 剪枝如果第一个数大于target了就没必要继续寻找四元组了num[i]如果为负数的负数相加会得到更小的负数所以nums[i]0; 防止溢出long sum (long)nums[i] nums[j] nums[left] nums[right];
int的取值范围是-2,147,483,648 ~ 2,147,483,647即-2^31 ~ 2^31-1。
long的取值范围是-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807即-2^63 ~ 2^63-1。 对于15.三数之和 (opens new window)双指针法就是将原本暴力O(n^3)的解法降为O(n^2)的解法四数之和的双指针解法就是将原本暴力O(n^4)的解法降为O(n^3)的解法。
代码
class Solution {public ListListInteger fourSum(int[] nums, int target) {ListListInteger ans new ArrayList();Arrays.sort(nums);for (int i 0; i nums.length - 3; i) {// 剪枝如果第一个数大于target了就没必要继续寻找四元组了num[i]如果为负数的负数相加会得到更小的负数所以nums[i]0if (nums[i] 0 nums[i] target) {break;}if (i 0 nums[i] nums[i - 1]) {continue;}for (int j i 1; j nums.length - 2; j) {// i变成了三数之和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];// 防止溢出long sum (long)nums[i] nums[j] nums[left] nums[right];if (sum target) {ans.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;}right--;left;} else if (sum target) {right--;} else if (sum target) {left;}}}}return ans;}
}
复杂度分析
时间复杂度: O(n^3)空间复杂度: O(1)
