网站免费推广策划方案,马鞍山天立建设网站,近年网络营销成功案例,个人网站备案要多久目录 454. 四数相加 II题目描述做题思路参考代码 383. 赎金信题目描述做题思路参考代码 15. 三数之和题目描述参考代码 18. 四数之和题目描述参考代码 454. 四数相加 II
题目描述
给你四个整数数组 nums1、nums2、nums3 和 nums4 #xff0c;数组长度都是 n #xff0c;请你… 目录 454. 四数相加 II题目描述做题思路参考代码 383. 赎金信题目描述做题思路参考代码 15. 三数之和题目描述参考代码 18. 四数之和题目描述参考代码 454. 四数相加 II
题目描述
给你四个整数数组 nums1、nums2、nums3 和 nums4 数组长度都是 n 请你计算有多少个元组 (i, j, k, l) 能满足
0 i, j, k, l nnums1[i] nums2[j] nums3[k] nums4[l] 0
做题思路
本题可以使用哈希表key 为 nums1[i] nums2[j] 的和value 为其出现的次数。然后再遍历 nums3 和 nums4如果存在 key 为 0-(nums3[k] nums4[l])那么结果就加对应的 value。
参考代码
class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {MapInteger,Integer mapnew HashMap();//新建hashmapint res0;int tmp;for(int i:nums1){for(int j:nums2){tmpij;if(map.containsKey(tmp))map.put(tmp,map.get(tmp)1);else map.put(tmp,1);}}for(int i:nums3){for(int j:nums4){tmpij;if(map.containsKey(0-tmp))resmap.get(0-tmp);}}return res;}
}383. 赎金信
题目描述
给你两个字符串ransomNote 和 magazine 判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以返回 true 否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
做题思路
本题可以使用哈希法先记录每个字母在magazine中出现的次数再减去每个字母在ransomNote中出现的次数若出现value0,则说明该字母magazine中没有。
参考代码
class Solution {public boolean canConstruct(String ransomNote, String magazine) {int[] recordnew int[26];for(char c:magazine.toCharArray())record[c-a];for(char c:ransomNote.toCharArray())record[c-a]--;for(int i:record)if(i0)return false;return true;}
}15. 三数之和
题目描述
给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请
你返回所有和为 0 且不重复的三元组。
注意 答案中不可以包含重复的三元组。
参考代码
class Solution {public ListListInteger threeSum(int[] nums) {ListListInteger result new ArrayList();Arrays.sort(nums);for (int i 0; i nums.length; i) {if (nums[i] 0) {return result;}if (i 0 nums[i] nums[i - 1]) {continue;}int left i 1;int right nums.length - 1;while (right left) {int sum nums[i] nums[left] nums[right];if (sum 0) {right--;} else if (sum 0) {left;} else {result.add(Arrays.asList(nums[i], nums[left], nums[right]));while (right left nums[right] nums[right - 1]) right--;while (right left nums[left] nums[left 1]) left;right--; left;}}}return result;}
}18. 四数之和
题目描述
给你一个由 n 个整数组成的数组 nums 和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] 若两个四元组元素一一对应则认为两个四元组重复
0 a, b, c, d na、b、c 和 d 互不相同nums[a] nums[b] nums[c] nums[d] target
你可以按 任意顺序 返回答案 。
参考代码
class Solution {public ListListInteger fourSum(int[] nums, int target) {ListListInteger result new ArrayList();Arrays.sort(nums);for (int i 0; i nums.length; i) {// nums[i] target 直接返回, 剪枝操作if (nums[i] 0 nums[i] target) {return result;}if (i 0 nums[i - 1] nums[i]) {continue;}for (int j i 1; j nums.length; j) {if (j i 1 nums[j - 1] nums[j]) {continue;}int left j 1;int right nums.length - 1;while (right left) {long sum (long) nums[i] nums[j] nums[left] nums[right];if (sum target) {right--;} else if (sum target) {left;} else {result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));while (right left nums[right] nums[right - 1]) right--;while (right left nums[left] nums[left 1]) left;left;right--;}}}}return result;}
}
