秋招算法刷题6

20240408

1.两数之和

在这里插入图片描述
（时间复杂度是O（n的平方））

public int[] twoSum(int[] nums, int target){int n=nums.length;         for(int i=0;i<n;i++){             for(int j=1;j<n;j++){                 if(nums[i][j]==target){                     return new int[]{i,j};}             }         }         return new int[0];  }

哈希表，时间复杂度O（N），空间复杂度O（N）.hash中先存一个，目标数减去存的，看数组中是否有这个数

public int[] twoSum(int[] nums, int target) {         
Map<Integer,Integer> hashtable= new HashMap<Integer,Integer>();      for(int i=0;i<nums.length;++i){            if(hashtable.containsKey(target-nums[i])){      return new int[]{hashtable.get(target-nums[i]),i};  }           hashtable.put(nums[i],i);    }       return new int[0];    }

（今天粘贴进来怎么都是乱的，真麻烦）

2.字母异位词分组

在这里插入图片描述

class Solution {         public List<List<String>> groupAnagrams(String[] strs) {             Map<String, List<String>> map = new HashMap<String, List<String>>();             for (String str : strs) {                 char[] array = str.toCharArray();                 Arrays.sort(array);                 String key = new String(array);                 List<String> list = map.getOrDefault(key, new ArrayList<String>());                 list.add(str);                 map.put(key, list);             }             return new ArrayList<List<String>>(map.values());         }     }

（这个粘贴我真的谢）

3.最长连续序列

在这里插入图片描述

public int longestConsecutive(int[] nums) {         Set<Integer> num_set =new HashSet<Integer>();         for(int num:nums){             num_set.add(num);         }         int longestStreak=0;         for(int num:num_set){             if(!num_set.contains(num-1)){                 int currentNum=num;                 int currentStreak=1;                 while(num_set.contains(currentNum+1)){                     currentNum+=1;                     currentStreak+=1;                 }                 longestStreak=Math.max(longestStreak,currentStreak);             }          }         return longestStreak;     }