454. 四数相加 II
题目描述
网络异常，图片无法展示
|
思路分析
将四个数组分成两两一对分别计算，前两个数组遍历想加结果放在 map中 ， key是值，value是出现的次数，最后在相加
代码展示
public static int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { int n = nums1.length, m, result = 0; Map<Integer,Integer> map = new HashMap<>(); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { m = nums1[i] + nums2[j]; map.put(m, map.getOrDefault(m,0) + 1); } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { m = nums3[i] + nums4[j]; result += map.getOrDefault( 0 - m, 0); } } return result; } 复制代码
提交结果
网络异常，图片无法展示
|
总结
个人思考有误，想多了导致第一次提交的时候报错，不该不该
383. 赎金信
题目描述
网络异常，图片无法展示
|
思路分析
这道题和 242.字母异位词做法思路一样
先创建一个 int利用下标来存储 magazine字母的个数，在遍历 ransomNote在响应下标减去，最后遍历 ints数组，判断有没有 < 0的值就可以了
代码展示
public static boolean canConstruct(String ransomNote, String magazine) { int[] ints = new int[26]; for (int i = 0; i < magazine.length(); i++) { ints[magazine.charAt(i) - 'a']++; } for (int i = 0; i < ransomNote.length(); i++) { ints[ransomNote.charAt(i) - 'a']--; } for (int anInt : ints) { if (anInt < 0){ return false; } } return true; } 复制代码
提交结果
网络异常，图片无法展示
|
15. 三数之和
题目描述
网络异常，图片无法展示
|
思路分析
注意题中只说返回元素，而不是下标
所以我们可以直接对当前数组进行排序，从左往右遍历，固定住下标为 i的数，下标为 （i - length）的数组让他们双指针去做判断
需要注意的是，当 nums[i] > 0的时候，证明后面都是正数，三数想加肯定不能为 0
相邻两个数相同时要跳过，不然统计的结果会有重复
代码展示
public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> result = new ArrayList<>(); Arrays.sort(nums); int left,right, sum; for (int i = 0; i < nums.length; i++) { if (nums[i] > 0){ break; } if (i > 0 && nums[i] == nums[i - 1]){ continue; } left = i + 1; right = nums.length - 1; while (left < right){ sum = nums[i] + nums[left] + nums[right]; if (sum == 0){ result.add(Arrays.asList(nums[i],nums[left], nums[right])); while(left < right && nums[right] == nums[right - 1]) right--; while(left < right && nums[left] == nums[left + 1]) left++; left++; right--; }else if (sum > 0){ right--; }else{ left++; } } } return result; } 复制代码
提交结果
网络异常，图片无法展示
|
总结
细节细节还是细节把控问题
18. 四数之和
题目描述
网络异常，图片无法展示
|
思路分析
和三数之和一样，固定一个点变成了固定两个点，双指针操作让四数值和暴力解法的时间复杂度： O（n^4）变成了 O（n^3）
细节细节还是细节，真的难搞
代码展示
public static List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> list = new ArrayList<>(); Arrays.sort(nums); for (int i = 0; i < nums.length; i++) { if (nums[i] > target && (nums[i] > 0 || target > 0)){ break; } if (i > 0 && nums[i] == nums[i - 1]){ continue; } for (int j = nums.length - 1; j > i + 2; j--) { if (j < nums.length - 1 && nums[j] == nums[j + 1]){ continue; } int left = i + 1, right = j - 1; while(left < right){ long sum =(long) nums[i] + nums[j] + nums[left] + nums[right]; if (sum > target){ right--; }else if (sum < target){ left++; }else{ list.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right])); while(left < right && nums[left] == nums[left + 1]) left++; while(left < right && nums[right] == nums[right - 1])right--; left++; right--; } } } } return list; } 复制代码
提交结果
网络异常，图片无法展示
|
总结
咱就说，细节决定成败，方向一直是对的，就是各种细节问题
