系列文章目录
目录
- 系列文章目录
- 454.四数相加II
- 使用HashMap法
- 383.赎金信
- 哈希解法（数组）
- 15.三数之和
- 双指针法
- 18.四数之和
- 双指针法
454.四数相加II
题解：该题和1.两数之和的方法是一样的，这个题的难点在于key和value分别是什么。key是相加的值，value是这个值出现的次数。怎么计算这个值出现的次数又是另一个难点了。需要用到Map接口的getDoDefault方法，getOrDefault(key,0)：找到key对应的value，如果key不存在，就返回0。
使用HashMap法
import java.util.HashMap;
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
HashMap<Integer, Integer> map = new HashMap<>();
//统计两个数组中的元素之和，同时统计出现的次数，放入map
for (int i = 0; i < nums1.length; i++) {
for (int j = 0; j < nums2.length; j++) {
int sum = nums1[i] + nums2[j];
/* if (!map.containsKey(sum)) {//如果没加过该key
map.put(sum, 1);
} else {//加过该key则替换value值，将value+1
map.put(sum, map.get(sum) + 1);
}*/
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
}
//统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数
int count = 0;
for (int i = 0; i < nums3.length; i++) {
for (int j = 0; j < nums4.length; j++) {
int sum = nums3[i] + nums4[j];
if (map.containsKey(-sum)) {
count += map.get(-sum);
}
}
}
return count;
}
}
//leetcode submit region end(Prohibit modification and deletion)
注：统计key值出现的次数，有两种方法改变value值。
①利用只能加入一个key，若重复加入key则替换value来实现。
if (!map.containsKey(sum)) {//如果没加过该key
map.put(sum, 1);
} else {//加过该key则替换value值，将value+1
map.put(sum, map.get(sum) + 1);
}
②通过getDoDefault方法实现。（快一些）
map.put(sum, getOrDefault(sum, 0) + 1);
383.赎金信
题解：因为两个字符串都是由小写字母组成的，所以说数据的范围是确定的，那么就可以用数组结构。用每个字符对应其数组下标，数组值就是每个字母出现的次数，最后遍历另一个字符串，需要的字母就-1，最后看结果数组的是否有负值，有负值说明字母是不够的，返回false。
哈希解法（数组）
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
//剪枝
if (ransomNote.length() > magazine.length()) {
return false;
}
int[] record = new int[26];
//遍历第一个字符串，通过record数据记录 magazine里各个字符出现次数
for (int i = 0; i < magazine.length(); i++) {
record[magazine.charAt(i) - 'a']++;
}
/*//遍历ransomNote+判断数组值是否为负
for (int i = 0; i < ransomNote.length(); i++) {
if(--record[ransomNote.charAt(i)-'a']<0){//只要有一个数组值为负数，就返回false
return false;
}
}*/
// 遍历ransomNote，在record里对应的字符个数做--操作
for (int i = 0; i < ransomNote.length(); i++) {
record[ransomNote.charAt(i) - 'a']--;
}
//判断数组值是否为负
for (int i = 0; i < record.length/*ransomNote.length()*/; i++) {
// 如果小于零说明ransomNote里出现的字符，magazine没有
if (record[i]/*record[ransomNote.charAt(i) - 'a']*/ < 0) {
return false;
}
}
return true;
}
}
注：从字符到数组下标的映射比较耗时间，故最后判断数组值是否为负时直接遍历record数组即可，不要再映射了。
15.三数之和
题解：在同一个数组中找一个三个数（这三个数的下标不同），相加和为0，这个三元组不能重复，但里面的元素可以重复。如果数组是 [0,0,1,1,-1,-1,-2]，则 [0,1,-1] 和[0,1,-1]不合法，但是[1,1,-2]合法。
双指针法
import java.util.ArrayList;
import java.util.Arrays;
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
//注意题目中方法要求返回<List<Integer>>泛型
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;
}
//去重a
//一定要有i>0条件，因若i=0，此时nums[i-1]=-1，数组越界异常
if (i > 0 && nums[i] == nums[i - 1]) {
continue;//跳过本次循环进入下次循环，不能i++因还会执行本次循环
}
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
//剪枝：排序之后如果最后一个元素小于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
if(nums[right]<0){
System.out.println("1111");
return result;
}
if (nums[i] + nums[left] + nums[right] > 0) {
right--;
} else if (nums[i] + nums[left] + nums[right] < 0) {
left++;
} else {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
// 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
while (left < right && nums[right] == nums[right - 1]) right--;
while (left < right && nums[left] == nums[left + 1]) left++;
right--;
left++;
}
}
}
return result;
}
}
//leetcode submit region end(Prohibit modification and deletion)
注：①题目中方法要求返回<List<Integer>>泛型，故在创建ArrayList时要注意。
②Arrays类里面包含了一系列静态方法，用于管理或操作数组，故调用sort方法对数组进行自然排序。
③剪枝操作：排序后，在遍历数组时，
-
如果三个数中最小的数即
a=nums[i]已经>0，则已不可能三个数之和为0，故可直接退出。for (int i = 0; i < nums.length; i++) { //剪枝：排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了 if (nums[i] > 0) { return result; } ... } -
如果最后一个元素
c=nums[right]已经<0，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了。while (left < right) { //剪枝：排序之后如果最后一个元素小于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了 if(nums[right]<0){ System.out.println("1111"); return result; } ... }
④对a进行去重时，一定要有i>0条件，因若i=0，此时nums[i-1]=-1，数组越界异常。
⑤对b=nums[left]，c=nums[right]的去重操作。
-
放在找到三元组之前，
[0，0，0]的情况，可能直接导致right<=left直接退出循环了，此时还没加入一个三元组，从而漏掉了[0，0，0]这种三元组。while (left < right) { // 去重复逻辑如果放在这里，0，0，0 的情况，可能直接导致 right<=left 了，从而漏掉了 0,0,0 这种三元组 /* while (right > left && nums[right] == nums[right - 1]) right--; while (right > left && nums[left] == nums[left + 1]) left++; */ if (...) ... } -
去重逻辑应该放在找到一个三元组之后，对
b、c去重。此时判断right是否与左边元素相等，若相等则跳过该左边的元素；判断left是否与右边元素相等，若相等则跳过该右边的元素。最后两行的right--; left++;不管b、c有没有重复都得有，其意味着三元组此时已经=0，不论单独移动哪一边，都不会再有=0的情况了，故必须得同时移动。
-
很多同学写本题的时候，去重的逻辑多加了 对
right和left的去重：nums[right] == nums[right + 1]其实比较的还是当前right指针即right + 1与左边元素right，因前面有个right--;，已经将right指针左移了，此时指向的是左边元素。nums[left] == nums[left - 1]同理。while (right > left) { if (nums[i] + nums[left] + nums[right] > 0) { right--; // 去重 right while (left < right && nums[right] == nums[right + 1]) right--; } else if (nums[i] + nums[left] + nums[right] < 0) { left++; // 去重 left while (left < right && nums[left] == nums[left - 1]) left++; } else { } }
因此时是在!=0的条件下去重的，不论是right还是left，即使去重了，去重后得到的right和left指针还是指向三元组!=0的元素。
18.四数之和
双指针法
