代码随想算法训练营day07：LeetCode(454)四数相加 II、LeetCode(383)赎金信、LeetCode(15)三数之和、LeetCode(18)四数之和
LeetCode(454)四数相加 II
题目
代码
import java.util.HashMap;
import java.util.Map;
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
//用哈希表map去做，两个数组考虑、两个数组映射、需要统计次数考虑value
HashMap<Integer,Integer> map1=new HashMap<>();
//统计次数
int count=0;
//先遍历nums1、nums2进行预处理
for (int i = 0; i < nums1.length; i++) {
for (int j = 0; j < nums2.length; j++) {
int tempdate=nums1[i]+nums2[j];
if(map1.containsKey(tempdate)){
map1.put(tempdate,map1.get(tempdate)+1);
}else{
map1.put(tempdate,1);
}
}
}
//相当于把数组nums1、nums2中的数组进行累加并存储到新的集合里面
//接着遍历另外两个数组，由于求和为0,逆向判断相反数是否在集合里面
for (int k = 0; k < nums3.length; k++) {
for (int l = 0; l < nums4.length; l++) {
int tempdata2=nums3[k]+nums4[l];
if(map1.containsKey(-(tempdata2))){
count=count+map1.get(-(tempdata2));//统计次数
}
}
}
return count;
}
}
LeetCode(383)赎金信
题目
代码
import java.util.HashMap;
import java.util.Map;
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
//设计Map集合----存放magazine
Map<String,Integer> map1=new HashMap<>();
for (int i = 0; i < magazine.length(); i++) {
String tempdate=String.valueOf(magazine.charAt(i));
if(map1.containsKey(tempdate)){
map1.put(tempdate,map1.get(tempdate)+1);
}else{
map1.put(tempdate, 1);
}
}
//相当于把magazine全部存到了集合里面
for (int j = 0; j < ransomNote.length(); j++) {
String tempdate1=String.valueOf(ransomNote.charAt(j));
if(map1.containsKey(tempdate1)){
map1.put(tempdate1, map1.get(tempdate1)-1);
if(map1.get(tempdate1)==0){
map1.remove(tempdate1);//判断抵消的数量，数量要是小于0之后，就删除数据
}
}else{
return false;
}
}
return true;
}
}
LeetCode(15)三数之和
题目
代码
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
//注意去重操作----方法使用双指针
List<List<Integer>> result=new ArrayList<>();
//给数组进行排序
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
//首先给i去重，i往后去重
if(nums[i]>0) {
return result;}//只要三个数字重复出现就算重复
if(i>0&&nums[i]==nums[i-1]) {
continue;}//后面出现的结果，前面肯定出现过
int left=i+1;//去数字重复[-1,-2,3]与[3,-1,-2]
int right=nums.length-1;
while(left<right){
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]));
List<Integer> list=new ArrayList<>();
Collections.addAll(list, nums[i],nums[left],nums[right]);
result.add(list);
left++;
right--;
//此时动left和right指针，动小指针
while(left<right&&nums[left]==nums[left-1]){
left++;}
while(left<right&&nums[right]==nums[right+1]){
right--;}
/* left++;
right--; */
}
}
}
return result;
}
}
LeetCode(18)四数之和
题目
代码
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
//注意去重操作----方法使用双指针
List<List<Integer>> result=new ArrayList<>();
//给数组进行排序
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
//首先给i去重，i往后去重
if(nums[i]>0) {
return result;}//只要三个数字重复出现就算重复
if(i>0&&nums[i]==nums[i-1]) {
continue;}//后面出现的结果，前面肯定出现过
int left=i+1;//去数字重复[-1,-2,3]与[3,-1,-2]
int right=nums.length-1;
while(left<right){
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]));
List<Integer> list=new ArrayList<>();
Collections.addAll(list, nums[i],nums[left],nums[right]);
result.add(list);
left++;
right--;
//此时动left和right指针，动小指针
while(left<right&&nums[left]==nums[left-1]){
left++;}
while(left<right&&nums[right]==nums[right+1]){
right--;}
/* left++;
right--; */
}
}
}
return result;
}
}
