今日学习的文章链接和视频链接
自己看到题目的第一想法
#（454.四数相加II ）
暴力解法：四层for循环。超时…拆解：两个一组分别进行两层for循环,细节不会实现了..
#（383. 赎金信 ）
1// 第一个思路： 2// 字符串转数组 3 4// map封装遍历判断ransomNote中每个字符出现的次数是否小于等于magazine与之对应的字符出现的次数 5 6// 第二个思路： 7// 因为都是英文小写字母，将ransomNote中每个字符出现的次数做记录； 8// 同时对magazine中的字符做记录，判断与之对应的字符出现的次数
#（15. 三数之和 ）
- 1// 排序
- 2// 前后指针 + 移动指针（具体实现有些复杂，逻辑不清晰）
- #（18. 四数之和）
双指针 + 两个循环判断
看完代码随想录之后的想法
#（454.四数相加II ）
逻辑：分两组，拆解着做。关键在于怎么存放数据；map很巧妙,具有封装性。
#（383. 赎金信 ）
暴力没想出来！！
和有效字母异位词同一个模板，拿来改改就能用。
#（15. 三数之和 ）
逻辑相似，但实现逻辑更清晰，通过＞0和＜0进行判断左右的移动，a去重细节清晰。
#（18. 四数之和）
多加一层for循环遍历，应注意去重剪枝的小细节。
自己实现过程中遇到哪些困难
#（454.四数相加II ）
key存放两组元素之和，value存放该和出现次数；
map.put()调用，map.getOrDefault(0 - i - j, 0)方法内涵等不了解；
增强for循环不是很了解，大概先背下来。
#（383. 赎金信 ）
基础语法不熟悉，需要记忆。如字符数组转换，字符偏移量位置字符检索操作。
#（15. 三数之和 ）
排序实现方式，a去重细节，其他两个数去重细节。
#（18. 四数之和）
首层for循环的剪枝操作，两层for循环去重细节
今日收获，记录一下自己的学习时长
3.5h
1// 自己实现：暴力 2class Solution { 3 public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { 4 int n = nums1.length; 5 int count = 0; 6 // 第一想法：四层for循环遍历判等，返回即可 7 for (int i = 0; i < n; i++) { 8 for (int j = 0; j < n; j++) { 9 for (int k = 0; k < n; k++) { 10 for (int l = 0; l < n; l++) { 11 if (nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0) { 12 count++; 13 } 14 } 15 } 16 } 17 } 18 return count; 19 } 20} 21 22// 自己实现：暴力二（编译没通过...越来越复杂，止损！） 23// class Solution { 24// public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { 25// int n = nums1.length; 26// int count = 0; 27// int m = n * n; 28// int[] res1 = new int[n * n]; 29// int[] res2 = new int[n * n]; 30 31// // 拆解 32// for (int i = 0; i < n; i++) { 33// for (int j = 0; j < n; j++) { 34// res1[m--] = nums1[i] + nums2[j]; 35// } 36// } 37// for (int k = 0; k < n; k++) { 38// for (int l = 0; l < n; l++) { 39// res2[m--] = nums3[k] + nums4[l]; 40// } 41// } 42// for (int i = 0; i < m; i++) { 43// for (int j = 0; j < m; j++) { 44// if (res1[i] + res2[j] == 0) { 45// count++; 46// } 47// } 48// } 49 50// return count; 51// } 52// } 53 54class Solution { 55 public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { 56 // 初始化结果变量 57 int res = 0; 58 // 创建一个 HashMap，用于存储两个数组中元素之和及其出现的次数 59 Map<Integer, Integer> map = new HashMap<Integer, Integer>(); 60 61 // 统计 nums1 和 nums2 数组中元素之和的情况，将结果存入 map 62 for (int i = 0; i < nums1.length; i++) { 63 for (int j = 0; j < nums2.length; j++) { 64 int sum = nums1[i] + nums2[j]; 65 // 将 sum 作为 key，将其出现次数作为 value 存入 map 66 // 如果 sum 已经在 map 中，取出其对应的 value 加 1，否则默认值为 0 67 map.put(sum, map.getOrDefault(sum, 0) + 1); 68 } 69 } 70 71 // 统计 nums3 和 nums4 数组中元素之和的情况，查找 map 中是否存在与之相加为 0 的情况，并将次数累加到结果变量 res 上 72 for (int i : nums3) { 73 for (int j : nums4) { 74 // 查找与当前元素 i 和 j 相加为 0 的情况在 map 中的次数，并将次数加到结果变量 res 上 75 res += map.getOrDefault(0 - i - j, 0); 76 } 77 } 78 79 // 返回最终结果 80 return res; 81 } 82}
#（383. 赎金信 ）
1// 枚举暴力输出 2class Solution { 3 public boolean canConstruct(String ransomNote, String magazine) { 4 char[] str1 = ransomNote.toCharArray(); 5 char[] str2 = magazine.toCharArray(); 6 for (int i = 0; i < str1.length; i++) { 7 for (int j = 0; j < str2.length; j++) { 8 if (str1[i] == str2[j]) { 9 str1[i] = '0'; 10 str2[j] = '0'; 11 continue; 12 } 13 } 14 } 15 16 for (int i = 0; i < str1.length; i++) { 17 if (str1[i] != '0') { 18 return false; 19 } 20 } 21 return true; 22 } 23} 24 25//借鉴242.有效的字母异位词的模板 26class Solution { 27 public boolean canConstruct(String ransomNote, String magazine) { 28 int[] res = new int[26]; 29 for (int i = 0; i < ransomNote.length(); i++) { 30 res[ransomNote.charAt(i) - 'a']--; 31 } 32 33 for (int i = 0; i < magazine.length(); i++) { 34 res[magazine.charAt(i) - 'a']++; 35 } 36 for (int i = 0; i < res.length; i++) { 37 if (res[i] < 0) { 38 return false; 39 } 40 } 41 42 return true; 43 } 44}
#（15. 三数之和 ）
1class Solution { 2 public List<List<Integer>> threeSum(int[] nums) { 3 // 排序 4 Arrays.sort(nums); 5 List<List<Integer>> res = new ArrayList<>(); 6 7 // 前后指针 + 移动指针 8 9 for (int i = 0; i < nums.length; i++) { 10 if (nums[i] > 0) { 11 return res; 12 } 13 // 去重第一个数 14 if (i > 0 && nums[i] == nums[i - 1]) { 15 continue; 16 } 17 18 int left = i + 1; 19 int right = nums.length - 1; 20 while (right > left) { 21 int sum = nums[i] + nums[left] + nums[right]; 22 if (sum > 0) { 23 right--; 24 } else if (sum < 0) { 25 left++; 26 } else { 27 res.add(Arrays.asList(nums[i], nums[left], nums[right])); 28 // right去重 29 while (left < right && nums[right] == nums[right - 1]) { 30 right--; 31 } 32 // left去重 33 while (left < right && nums[left] == nums[left + 1]) { 34 left++; 35 } 36 // 加入和为 0 的元素后，right--，而left不变，此时，和为负数。所以两者同时移动。 37 right--;; 38 left++; 39 40 } 41 } 42 } 43 return res; 44 } 45}
#（18. 四数之和）
1class Solution { 2 public List<List<Integer>> fourSum(int[] nums, int target) { 3 List<List<Integer>> result = new ArrayList<>(); 4 Arrays.sort(nums); 5 6 for (int i = 0; i < nums.length; i++) { 7 8 // nums[i] > target 直接返回, 剪枝操作 9 if (nums[i] > 0 && nums[i] > target) { 10 return result; 11 } 12 13 if (i > 0 && nums[i - 1] == nums[i]) { // 对nums[i]去重 14 continue; 15 } 16 17 for (int j = i + 1; j < nums.length; j++) { 18 19 if (j > i + 1 && nums[j - 1] == nums[j]) { // 对nums[j]去重 20 continue; 21 } 22 23 int left = j + 1; 24 int right = nums.length - 1; 25 while (right > left) { 26 // nums[k] + nums[i] + nums[left] + nums[right] > target int会溢出 27 long sum = (long) nums[i] + nums[j] + nums[left] + nums[right]; 28 if (sum > target) { 29 right--; 30 } else if (sum < target) { 31 left++; 32 } else { 33 result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right])); 34 // 对nums[left]和nums[right]去重 35 while (right > left && nums[right] == nums[right - 1]) right--; 36 while (right > left && nums[left] == nums[left + 1]) left++; 37 38 left++; 39 right--; 40 } 41 } 42 } 43 } 44 return result; 45 } 46}
