1. LeetCode 454.四数相加II
1.1 思路
- 这题不需要考虑去重并且不需要知道具体哪4个数，求出数量count即可
- 遍历A、B数组把a+b的值放入集合的key中并且统计a+b出现过几次然后放入集合的value中，在遍历C、D数组时判断集合里是否有想要的元素（找匹配项），因此用map
- 遍历C、D数组时从map中查找0-(a+b)的值出现过几次
- 遍历到的次数后count+什么呢？应该是加(a+b)的value值
- 为什么不先遍历A数组然后再遍历BCD三个数组呢？如果是这种方式遍历A时复杂度是N，遍历BCD时复杂度是N^3，这样总的时间复杂度是N^3。而上述的先遍历AB是N^2，再遍历CD是N^2，这样总的时间复杂度是N^2
1.2 代码
class Solution { public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { int res = 0; Map<Integer, Integer> map = new HashMap<Integer, Integer>(); //统计两个数组中的元素之和，同时统计出现的次数，放入map for (int i : nums1) { for (int j : nums2) { int sum = i + j; map.put(sum, map.getOrDefault(sum, 0) + 1); } } //统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数 for (int i : nums3) { for (int j : nums4) { res += map.getOrDefault(0 - i - j, 0); } } return res; } }
2. LeetCode 383. 赎金信
2.1 思路
- 因为题目说只有小写字母，那可以采用空间换取时间的哈希策略，用一个长度为26的数组来记录magazine里字母出现的次数。
- 然后再用ransomNote去验证这个数组是否包含了ransomNote所需要的所有字母。
- 你可能想，用数组干啥，都用map完事了，其实在本题的情况下，使用map的空间消耗要比数组大一些的，因为map要维护红黑树或者哈希表，而且还要做哈希函数，是费时的！数据量大的话就能体现出来差别了。 所以数组更加简单直接有效！
2.2 代码
class Solution { public boolean canConstruct(String ransomNote, String magazine) { // shortcut if (ransomNote.length() > magazine.length()) { return false; } // 定义一个哈希映射数组 int[] record = new int[26]; // 遍历 for(char c : magazine.toCharArray()){ record[c - 'a'] += 1; } for(char c : ransomNote.toCharArray()){ record[c - 'a'] -= 1; } // 如果数组中存在负数，说明ransomNote字符串总存在magazine中没有的字符 for(int i : record){ if(i < 0){ return false; } } return true; } }
3. LeetCode 15. 三数之和
3.1 思路
- 求三数之和为0，这个三元组要去重（难点）用双重for循环比那里寻找a+b的值，存放到map中，然后让寻求0-(a+b)的值是否在map出现过，但这样去重比较复杂。
- 双指针法：我们将数组排序后，用for循环遍历i的位置表示a，然后在i+1的位置用left表示b，arr.length-1的位置用right表示c，然后用nums[i]+nums[left]+nums[right]求和
- 如果＞0，则让right--，因为我们是排好序的，最右边的是最大的，此时>0，所以让最大的数变小，才能让和变小
- 如果<0，则让left++，因为我们是排好序的，最左边的是最小的，此时<0，所以让最小的数变大，才能让和变大
- 如果=0，则把这三个位置的数放入二维数组result中
- 细节在去重：abc三个数都是要去重，如果排好序后，nums[i]就>0就直接return，因为这是三元组里第一个数，都大于0就没法和为0了
- 去重a：nums[i]==nums[i+1]这种去重方式是判断了结果集里是否有相同元素，但结果集是可以有相同元素的；nums[i]==nums[i-1]这种去重方式是判断了i的前一个里是否有相同元素，这样判断的话是说明这两个元素如果已经用到了，就不能再用了，直接continue跳过，这样才对，并且这里要加个i>0&&的条件，避免出现下标为负的情况
- 去重b、c：因为left=i+1，right=arr.length-1；while(right>left)这里不要等于号，有等于号的话就是两个指针指向同个数了，那就少了一个数了
- while(right>left&&nums[right]==nums[right-1])那就继续right--while(right>left&&nums[left]==nums[left+1])那就继续left++
3.2 代码
class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> result = new ArrayList<>(); Arrays.sort(nums); // 找出a + b + c = 0 // a = nums[i], b = nums[left], c = nums[right] for (int i = 0; i < nums.length; i++) { // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了 if (nums[i] > 0) { return result; } if (i > 0 && nums[i] == nums[i - 1]) { // 去重a 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])); // 去重逻辑应该放在找到一个三元组之后，对b 和 c去重 while (right > left && nums[right] == nums[right - 1]) right--; while (right > left && nums[left] == nums[left + 1]) left++; right--; left++; } } } return result; } }
4. LeetCode 18. 四数之和
4.1 思路
- 这里延续了三数之和的思路，同理第一个位置k（第一个for循环），下一个位置i（嵌套在第一个for循环），再下一个位置left，最后一个位置right，并且先排好序
- 对第一个数剪枝：如果nums[k]>target&&nums[k]>0&&target>0，这样才可以break，因为如果两个都为负数的情况，比如四个数为{-4，-1，0，0}，target是5，这样的话如果不满足上述条件，就错过这个结果集了
- 对第一个数去重：if(k>0&&nums[k]==nums[k-1]那就continue跳过
- 对第二个数剪枝：此时将第一、二个数字作为一个整体，如果nums[i]+nums[k]>target&&target>0，这样也可以break
- 对第二个数去重：if(i>k+1&&nums[i]==nums[i-1]那就continue跳过，因为i是在k后一个位置的
- 下面的去重就是上面三数之和一样的了
4.2 代码
class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> 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]) { // 对nums[i]去重 continue; } for (int j = i + 1; j < nums.length; j++) { if (j > i + 1 && nums[j - 1] == nums[j]) { // 对nums[j]去重 continue; } int left = j + 1; int right = nums.length - 1; while (right > left) { // nums[k] + nums[i] + nums[left] + nums[right] > target int会溢出 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])); // 对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; } }
