第一题454.四数相加II
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
拿到题有点懵，第一时间想的是暴力，4个for循环，但想着一定会超时就没有实现直接看了题解
先遍历前两个数组求出所有可能的和，存入map中，两数之和为key，出现的次数作为value
再遍历后两个数组看看在map中是否有匹配(四数相加=0)的key，如果有，读取他的value，累加
public static int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
int sum;
Map<Integer, Integer> map = new HashMap<>();
// 把前两个数组中所有的和计算出来
for (int i = 0; i < nums1.length; i++) {
for (int j = 0; j < nums2.length; j++) {
sum = nums1[i] + nums2[j];//求出所有可能的和
if(!map.containsKey(sum)){
map.put(sum,1);//如果这个和是新的，加在map里
} else {
map.put(sum,map.get(sum)+1);//如果这个和曾在map中出现，其value+1
}
}
}
int count = 0;
//再来两个for循环遍历出后两个数组
for (int i = 0; i < nums3.length; i++) {
for (int j = 0; j < nums4.length; j++) {
sum = nums3[i] + nums4[j];
if(map.containsKey(0-sum)){
count += map.get(0-sum);//如果包含有匹配的key，读出他的value
}
}
}
return count;
}
时间复杂度为O(n^2)
第二题383. 赎金信
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
ψ(｀∇´)ψ 我的思路
该说不说我真的喜欢这道题，完全get他的语境好吧
package hash;
import java.util.HashMap;
import java.util.Map;
public class CanConstruct {
public boolean canConstruct(String ransomNote, String magazine) {
// 先把杂志中的字母存在map中，以字母为key，次数为value
char[] mag = magazine.toCharArray();
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < mag.length; i++) {
if(!map.containsKey(mag[i])){
map.put(mag[i],1);
} else {
map.put(mag[i],map.get(mag[i])+1);
}
}
// 遍历赎金信的每一个字母
char[] ran = ransomNote.toCharArray();
for (int i = 0; i < ran.length; i++) {
if(!map.containsKey(ran[i])){
return false;//如果赎金信中的字母没有在杂志中出现，返回false（这本不行，换一本拼吧
} else {
map.put(ran[i],map.get(ran[i])-1);//杂志中的字母用一个少一个
if(map.get(ran[i])==0){
map.remove(ran[i]);//用完就移除该字母的key
}
}
}
return true;
}
}
时间复杂度为O(n)
第三题15. 三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0。
请你返回所有和为 0 且不重复的三元组。
拿到题就没什么思路，也不难为自己，直接看视频，大概看了个思路，双指针问题
通过遍历数组来确定三个变量中的一个，另外两个用双指针遍历
这道题要考虑的地方挺碎的，实现的时候真的是太痛苦了
package hash;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class ThreeSum {
public static List<List<Integer>> threeSum(int[] nums) {
int left, right;
List<List<Integer>> res = new ArrayList<>();
List<Integer> list = null;
Arrays.sort(nums);//给数组排序
for (int i = 0; i < nums.length-2; i++) {//遍历数组(结束条件到数组长度-2，因为后面还要left和right)
if (nums[i] > 0) {
continue;//剪枝
}
if (i > 0 && nums[i] == nums[i - 1]) {
continue;//去重
}
left = i + 1;//让left指针指向i的下一个元素的地址
right = nums.length - 1;//让right指针指向数组的最后一个元素的地址
while (left < right) {
if (nums[i] + nums[left] + nums[right] == 0) {
list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[left]);
list.add(nums[right]);//把三元组存入list
res.add(list);//把list添加到res
while (left<right&&nums[left+1]==nums[left]){
left++;//去重
}
left++;
while (left<right&&nums[right-1]==nums[right]){
right--;//去重
}
right--;
} else if (nums[i] + nums[left] + nums[right] > 0) {
while (left<right&&nums[right-1]==nums[right]){
right--;//去重
}
right--;
} else if (nums[i] + nums[left] + nums[right] < 0) {
while (left<right&&nums[left+1]==nums[left]){
left++;//去重
}
left++;
}
}
}
return res;
}
public static void main(String[] args) {
int[] nums = new int[]{0,0,0};
threeSum(nums);
}
}
时间复杂度为O(n^2)
偶买噶，下一题是四数之和我真的栓Q了
第四题18. 四数之和
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
ψ(｀∇´)ψ 我的思路
四数之和嘛，不就是三树之和外面包一个for循环就好啦
然而到实现的时候我真的栓Q了好吧，太多临界条件，思路都写在注释里了
package hash;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class FourSum {
public static List<List<Integer>> fourSum(int[] nums, int target) {
int left, right;
List<List<Integer>> res = new ArrayList<>();
List<Integer> list = null;
Arrays.sort(nums);//给数组排序
for (int i = 0; i < nums.length; i++) {//-3是因为后面还有仨数呢
if(nums[i]>0&&target<0){
return res;
}
if (target>0 && nums[i]>0 && nums[i] > target) {
return res;//剪枝
}
if (i > 0 && nums[i] == nums[i - 1]) {
continue;//去重
}
for (int j = i+1; j < nums.length; j++) {//-2是因为后面还有两个数
//两层循环确定两个数(我也知道时间复杂度高，但没办法啊，咱不是只有双指针嘛
if (target>0 && nums[j]>0 && nums[i]+nums[j] > target) {
continue;//剪枝
}
if (j > i+1 && nums[j] == nums[j - 1]) {
continue;//去重
}
left = j + 1;//让left指针指向i的下一个元素的地址
right = nums.length - 1;//让right指针指向数组的最后一个元素的地址
while (left < right) {
if (nums[i] + nums[j] + nums[left] + nums[right] == target) {
list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[j]);
list.add(nums[left]);
list.add(nums[right]);//把四元组存入list
res.add(list);//把list添加到res
while (left<right&&nums[left+1]==nums[left]){
left++;//去重
}
left++;
while (left<right&&nums[right-1]==nums[right]){
right--;//去重
}
right--;
} else if (nums[i] + nums[j] + nums[left] + nums[right] > target) {
while (left<right&&nums[right-1]==nums[right]){
right--;//去重
}
right--;
} else if (nums[i] + nums[j] + nums[left] + nums[right] < target) {
while (left<right&&nums[left+1]==nums[left]){
left++;//去重
}
left++;
}
}
}
}
return res;
}
public static void main(String[] args) {
int[] nums = new int[]{1000000000,1000000000,1000000000,100000000};
fourSum(nums,-294967296);
}
}
时间复杂度为O(n^3)
一般我写代码的思路就是先把程序整个顺下来然后debug把小的地方修改修改，这题真的改到我怀疑人生
这是第一次提交，找了下原因，是里层循环的一个剪枝操作，我直接返回res，造成结果不全，改成continue了之后，就多通过了4个测试用例，变成了这样
不管我怎么改临界条件最后一个测试用例始终通不过，我只好又专门为他写了一段代码（私人定制）
if(nums[i]>0&&target<0){
return res;
}
血条已空
总结
为什么后两道双指针的题目会出现在哈希表里啊，就是看我做哈希表做的太快乐是吧
今天的第一道题还是把哈希表的优点体现的挺到位的，第二题有趣但简单，后两题我是看了思路后把代码实现的，我看到双指针的章节也有这两题，希望到时候可以独立做出来
看到明天的题目是字符串，哈哈开心，我现在真的需要字符串来回回血
明天早点起，别再磨叽了♀️
