一、LeetCode 454 四数相加II
题目链接：454.四数相加II
https://leetcode.cn/problems/4sum-ii/description/
思路：建立HashMap，Key存储nums1、nums2数对之和，Value存储数对和出现次数，再遍历nums3、nums4数对确定答案。
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Map<Integer,Integer> map = new HashMap<>(); //key存放a、b两数之和，value存放两数之和出现的次数
int n = nums1.length;
int ans = 0;
//存储nums1、nums2各数之和
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
int sum = nums1[i] + nums2[j];
if(map.containsKey(sum)){
int num = map.get(sum);
map.put(sum,num+1);
}else{
map.put(sum,1);
}
}
}
//检验nums3和nums4中有多少符合条件的数对
for(int i = 0; i < n ;i++){
for(int j = 0; j < n; j++){
int sum2 = nums3[i] + nums4[j];
if(map.containsKey(0-sum2)){
ans += map.get(0-sum2); //检测出符合条件的元组1*num
}
}
}
return ans;
}
}二、LeetCode 383 赎金信
题目链接：383.赎金信https://leetcode.cn/problems/ransom-note/description/
思路一：使用HashMap，Key存储字符，Value存储字符出现次数；分别遍历magazine与ransomNote，判断是否可行。
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int rlen = ransomNote.length();
int mlen = magazine.length();
if(mlen < rlen){
return false;
}
Map<Character,Integer> map = new HashMap<>(); //key存储字符，value存储magazine字符出现次数
for(int i = 0; i < mlen; i++){
Character temp = magazine.charAt(i);
if(map.containsKey(temp)){
map.put(temp,map.get(temp)+1);
}else{
map.put(temp,1);
}
}
for(int i = 0; i < rlen; i++){
Character temp = ransomNote.charAt(i);
if(map.containsKey(temp)){
int num = map.get(temp);
if(num == 1){
map.remove(temp);
}else{
map.put(temp,num-1);
}
}else{
return false;
}
}
return true;
}
}思路二：自建字典 alp[] = new int[26]。
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int rlen = ransomNote.length();
int mlen = magazine.length();
if(rlen > mlen){
return false;
}
int[] alp = new int[26]; //自建字典
for(int i = 0; i < mlen; i++){
alp[magazine.charAt(i) - 'a']++;
}
for(int i = 0; i < rlen ; i++){
if(alp[ransomNote.charAt(i)-'a'] == 0){
return false;
}else{
alp[ransomNote.charAt(i)-'a']--;
}
}
return true;
}
}三、LeetCode 15 三数之和
题目链接：15.三数之和https://leetcode.cn/problems/3sum/description/
思路：先对数组进行排序，设置双指针遍历并进行去重操作，得出不重复的三元组序列。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<>();
for(int i = 0; i < nums.length; i++){
//排序后第一个数就大于0，不存在符合题意的答案
if(nums[i] > 0){
return ans;
}
if(i > 0 && nums[i] == nums[i-1]){
continue;
}
int left = i+1;
int right = nums.length - 1;
while(right > left){
if(nums[i] + nums[left] + nums[right] > 0){
right--;
}else if(nums[i] + nums[left] + nums[right] < 0){
left++;
}else{
//去重逻辑应放到添加第一个三元组之后
List<Integer> list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[left]);
list.add(nums[right]);
ans.add(new ArrayList(list));
//去重
while(right > left && nums[right] == nums[right-1]){
right--;
}
while(right > left && nums[left] == nums[left+1]){
left++;
}
//双指针收缩
right--;
left++;
}
}
}
return ans;
}
}补充：此题不会，看的卡哥思路，明日复习。
四、LeetCode 18 四数之和
题目链接：18.四数之和https://leetcode.cn/problems/4sum/submissions/499470243/
思路：与三数之和类似，排序、剪枝、双指针遍历、去重；掌握不熟练，需要多加练习。
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
//先给数组排序
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<>();
for(int i = 0; i < nums.length; i++){
//一级剪枝处理
if(nums[i] > target && nums[i] >= 0){ //数组已按增序排列，后边的数都大于target且大于0
break;
}
//num[i]去重
if(i > 0 && nums[i] == nums[i-1]){
continue;
}
for(int j = i+1; j < nums.length; j++){
//二级剪枝
if(nums[i] + nums[j] > target && nums[i] + nums[j] > 0){
break;
}
//nums[j]去重
if(j > i+1 && nums[j] == nums[j-1]){
continue;
}
int left = j+1;
int right = nums.length-1;
while(left < right){
if(nums[i] + nums[j] + nums[left] + nums[right] > target){
right--;
}else if(nums[i] + nums[j] + nums[left] + nums[right] < target){
left++;
}else{
List<Integer> list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[j]);
list.add(nums[left]);
list.add(nums[right]);
ans.add(new ArrayList(list));
//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 ans;
}
}五、今日小结
三数之和、四数之和需要多加练习，双指针没能很好地运用呜呜呜；明天争取少睡一些^*^，加油ovo！
