将过去和羁绊全部丢弃，不要吝惜那为了梦想流下的泪水。——路飞
文章目录
- 1. 两数之和
-
- 第一种：直接暴力查找，感觉大家都会
- 第二种是：使用哈希表
- 454. 四数相加 II
-
- 哈希表
- 15. 三数之和
-
- 双指针法
- 18. 四数之和
文章图片
~~~~~时隔 4 4 4个月，再次回到起点，做起了二数之和，还记得第一次遇见力扣，是因为学长给我们这些新生做后端培训时，就挑了这一道题给我练练手，当时心高气傲，一看是简单题，就觉得自己会秒杀，以为自己用 c c c语言做过洛谷 30 30 30多道题，一遍就可以 A C AC AC，md,现实是
文章图片
~~~~~以为通过的代码是自己写的？ 其实是自己不会了，然后复制粘贴才完事（现在也是这种水平 哭呜呜呜）而且中间的java编译错误，是自己照搬时还写错了，真的蠢！那时还没决定学后端，java确实不会，同时leetcode的题目答题与其他平台不同，所以彻底懵了！！我当时就当了鸵鸟，把头埋进了沙子，不会做，连暴力破解都不会，也不去理解题解，时隔4个月才再次拿起。
【被LeetCode锤爆的日子|【LeetCode】 梦的开始---两数之和】菜鸟的经历就是这样。呜呜呜
文章图片
一般来说哈希表都是用来快速判断一个元素是否出现集合里。1. 两数之和
有人相爱，有人夜里开车看海，有人leetcode第一题都做不出来。
文章图片
第一种：直接暴力查找，感觉大家都会
class Solution {
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
for (int i = 0;
i < n;
++i) {
for (int j = i + 1;
j < n;
++j) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
return new int[0];
}
}
第二种是：使用哈希表 ~~~~~将查找的时间复杂度减少，主要是在查找target - num[i]上，不需要再次遍历数组，哈希表的key为数组的值，value为数组的下标
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] sum = new int[2];
Map map = new HashMap<>();
for(int i =0;
i 
文章图片
454. 四数相加 II
文章图片
哈希表 ~~~~~使用哈希表，让四数之和变为两数之和，四个数，当两两相加，就变成了两个数，那就是二数之和。
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
int num = 0;
Mapmap = new HashMap<>();
for(int i : nums1){
for(intj : nums2){
int temp = i + j;
if(!map.containsKey(temp)){
map.put(temp,1);
}else{
map.put(temp,map.get(temp) +1);
}
}
}for( int i : nums3){
for(int j : nums4){
int t = i + j;
int temp = 0 - t;
if(map.containsKey(temp)){
num +=map.get(temp);
}
}
}
return num;
}
}
15. 三数之和
文章图片
双指针法 ~~~~~我用了哈希表，发现很难实现，但双指针法很可以！
双指针法一定要排序1.首先，让相加之和第一个数永远小于等于0
2.创建双指针，left为第一个数的右边，right为数组的最右边,
3.在right >left里，不断循环
class Solution {
public List> threeSum(int[] nums) {
List> list = new ArrayList<>();
Arrays.sort(nums);
for( int i = 0;
i 0){
return list;
}
if(i >0 && nums[i] == nums[i-1]){//这里是i -1,不是i+1
continue;
//去重
}
int left = i +1;
int right = nums.length -1;
while(right >left){
int sum = nums[i] + nums[left] +nums[right];
if(sum > 0){
right--;
}else if(sum < 0){
left++;
}else{
list.add(Arrays.asList(nums[i],nums[left],nums[right]));
//去重
while(left 18. 四数之和
文章图片
~~~~~和三数之和差不多，套娃游戏，再加一个for循环
class Solution {
public List> fourSum(int[] nums, int target) {
List> list = new ArrayList<>();
Arrays.sort(nums);
for(int i = 0 ;
i0 && nums[i]==nums[i-1])
continue;
for(int j = i + 1;
j i+1 &&nums[j]==nums[j -1])
continue;
int left = j + 1;
int right = nums.length-1;
while(left < right){
int sum = nums[i] + nums[j] +nums[left] + nums[right];
if(sum >target){
right--;
}else if(sum left&& nums[right] ==nums[right -1]) right--;
while(right >left&& nums[left] == nums[left+1]) left++;
left++;
right--;
}
}
}
}
return list;
}
}
文章图片
推荐阅读
- leetcode|【LeetCode】set集合+哈希表+快慢指针
- dbcp|这份新年豪礼面试锦囊，真舍不得给你们！
- leetcode|Leetcode哈希表题目总结（持续更新）
- hash|这一篇，带你十分钟深入理解HashMap源码
- leetcode|【leetcode刷题】哈希表-第1篇
- 散列表|leetcode哈希表java
- 存储|哈夫曼树（Huffman tree）及哈夫曼编码
- 面试|大厂谁不想去呢（一个月面试+复习+总结-我成功斩获offer）
- leetcode算法|LeetCode——哈希表篇