将过去和羁绊全部丢弃，不要吝惜那为了梦想流下的泪水。——路飞

文章目录

• 1. 两数之和
• • 第一种：直接暴力查找，感觉大家都会
  • 第二种是：使用哈希表
• 454. 四数相加 II
• • 哈希表
• 15. 三数之和
• • 双指针法
• 18. 四数之和

      ~~~~~       时隔$4$个月，再次回到起点，做起了二数之和，还记得第一次遇见力扣，是因为学长给我们这些新生做后端培训时，就挑了这一道题给我练练手，当时心高气傲，一看是简单题，就觉得自己会秒杀，以为自己用$c$语言做过洛谷$30$多道题，一遍就可以$AC$，md,现实是

      ~~~~~       以为通过的代码是自己写的？ 其实是自己不会了，然后复制粘贴才完事（现在也是这种水平 哭呜呜呜）而且中间的java编译错误，是自己照搬时还写错了，真的蠢！那时还没决定学后端，java确实不会，同时leetcode的题目答题与其他平台不同，所以彻底懵了！！我当时就当了鸵鸟，把头埋进了沙子，不会做，连暴力破解都不会，也不去理解题解，时隔4个月才再次拿起。

菜鸟的经历就是这样。呜呜呜

一般来说哈希表都是用来快速判断一个元素是否出现集合里。

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<Integer,Integer> map = new HashMap<>(); for(int i =0; i<nums.length;i++){     int temp = target - nums[i];     if(map.containsKey(temp)){  sum[0] = i;  sum[1] = map.get(temp);  return  sum;//这里直接return ,减少了时间复杂度     }     map.put(nums[i],i); }  return sum;    }}

454. 四数相加 II

哈希表

      ~~~~~       使用哈希表，让四数之和变为两数之和，四个数，当两两相加，就变成了两个数，那就是二数之和。

class Solution {    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { int num = 0;  Map<Integer,Integer>  map = new HashMap<>();  for(int i : nums1){      for(int  j : 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<List<Integer>> threeSum(int[] nums) { List<List<Integer>> list = new ArrayList<>(); Arrays.sort(nums); for( int i = 0; i<nums.length;i++){     if(nums[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 <right && nums[right] ==nums[right-1]) right--; while(left <right && nums[left] == nums[left+1])  left++; left++; right--;     }} } return list;    }}

18. 四数之和

      ~~~~~       和三数之和差不多，套娃游戏，再加一个for循环

class Solution {    public List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> list = new ArrayList<>(); Arrays.sort(nums); for(int i = 0 ;i<nums.length;i++){     if(i>0 && nums[i]==nums[i-1])continue;     for(int j = i + 1;j <nums.length;j++){  if(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 <target){   left++;      }else{   list.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));   while(right >left&& nums[right] ==nums[right -1]) right--;   while(right >left&& nums[left] == nums[left+1]) left++;   left++;   right--;      }  }     } } return list;    }}