代码随想录算法训练营第六天 | LeetCode 454(四数相加II) LeetCode 383(赎金信) LeetCode 15(三数之和) LeetCode 18(四数之和)
454：四数相加II
首先定义 一个map，key放a和b两数之和，value放a和b两数之和出现的次数。
遍历nums1和nums2数组，统计两个数组元素之和，和出现的次数，放到map中。
定义int变量resCount，用来统计 a+b+c+d = 0 出现的次数。
在遍历nums3和nums4数组，找到如果 -(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。
最后返回统计值 resCount
import java.util.HashMap;
import java.util.Map;
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Map<Integer,Integer> res = new HashMap<Integer,Integer>();
int resCount = 0;
for (int num1 : nums1) {
for (int num2 : nums2) {
Integer count = res.get(num1+num2);
res.put(num1 + num2,null == count ? 1 : ++count);
}
}
for (int num3 : nums3) {
for (int num4 : nums4) {
if(res.containsKey(-(num3+num4))){
resCount += res.get(-(num3+num4));
}
}
}
return resCount;
}
}
383：赎金信
题目意思：用magazine中的小写字母去组成ransomNote，且magazine中的元素不可重复使用
用一个长度为26的数组来记录magazine里字母出现的次数。
然后再用ransomNote去验证这个数组是否包含了ransomNote所需要的所有字母。
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
//判空
if(ransomNote == null){
return false;
}
if(magazine == null){
return false;
}
//当magazine的长度小于ransomNote时，直接返回false
if (ransomNote.length() > magazine.length()) {
return false;
}
int length = Math.max(ransomNote.length(), magazine.length());
int rLen = ransomNote.length();
int mLen = magazine.length();
int[] array = new int[26];
//这里维护array这个记录数组
for(int i = 0; i < length; i++){
//记录ransomNote当前索引元素
if(i < rLen){
array[ransomNote.charAt(i) - 'a']++;
}
//消费
if(i < mLen){
array[magazine.charAt(i) - 'a']--;
}
}
//检查array
for(int i = 0; i < 26; i++){
//当数组有一个索引位置值大于0时 就意味着magazine提供满足不了ransomNote的需要
if(array[i] > 0){
return false;
}
}
return true;
}
}
15：三数相加
import java.util.ArrayList;
import java.util.List;
import java.util.Arrays;
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
//先对数组进行排序（其实感觉也可以不用 但不用的话后面的剪枝条件要进行修改）
Arrays.sort(nums);
//排序后 若第一个元素直接大于0 那么可以直接返回
if(nums[0] > 0 ){
return result;
}
//双指针
int left;
int right;
//循环条件 因为是三数之和 那么其实循环到nums.length - 2 就可以结束了
for (int i = 0; i < nums.length - 2; i++){
//去重 如果说前一个元素和当前元素相等的话
//那么就意味着这个元素的组合已经被记录了
if(i > 0 && nums[i] == nums[i - 1]){
continue;
}
left = i + 1;
right = nums.length - 1;
while(left < right){
//找到目标
if(nums[i] + nums[left] + nums[right] == 0){
//记录
List<Integer> temp = new ArrayList<Integer>();
temp.add(nums[i]);
temp.add(nums[left]);
temp.add(nums[right]);
result.add(temp);
//指针位移 + 去重
while(left < right && nums[right] == nums[right - 1 ]){
right--;
}
while(left < right && nums[left] == nums[left + 1 ]){
left++;
}
right--;
left++;
}
//因为是排序过后的数组 当三个数之和小于了0 那么就意味着需要增大left指针
else if(nums[i] + nums[left] + nums[right] < 0){
left++;
}
//同理 减小right
else{
right--;
}
}
}
return result;
}
}
18：四数相加
这道题和三数之和一个思路
也就是说你可以先确定一个索引值 把它当作三数之和等于的那个‘零’
那么就可以讲四数之和为零 降维成三数之和等于一个索引值
同理 五数之和，六数之和。。。就可以依次降维
import java.util.ArrayList;
import java.util.List;
import java.util.Arrays;
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
Arrays.sort(nums);
int left;
int right;
int tempTarget;
for (int k = 0; k < nums.length - 3; k++){
if(nums[k] > target && nums[k] > 0){
return result;
}
//这就是那个索引值
tempTarget = target - nums[k];
if(k > 0 && nums[k-1] == nums[k]){
continue;
}
//这里跟三数之和一个思路 只不过变成了三数之和等于tempTarget
for (int i = k + 1; i < nums.length - 2; i++){
if(i > k + 1 && nums[i] == nums[i - 1]){
continue;
}
left = i + 1;
right = nums.length - 1;
while(left < right){
if(nums[i] + nums[left] + nums[right] == tempTarget){
List<Integer> temp = new ArrayList<Integer>();
temp.add(nums[k]);
temp.add(nums[i]);
temp.add(nums[left]);
temp.add(nums[right]);
result.add(temp);
while(left < right && nums[right] == nums[right - 1 ]){
right--;
}
while(left < right && nums[left] == nums[left + 1 ]){
left++;
}
right--;
left++;
}else if(nums[i] + nums[left] + nums[right] < tempTarget){
left++;
}else{
right--;
}
}
}
}
return result;
}
}