LeetCode 热题100（JAVA）

LeetCode 热题100JAVA哈希1. 两数之和给定一个整数数组 nums和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那两个整数 并返回它们的数组下标。 你可以假设每种输入只会对应一个答案并且你不能使用两次相同的元素。 你可以按任意顺序返回答案。 示例 1 输入nums [2,7,11,15], target 9 输出[0,1] 解释因为 nums[0] nums[1] 9 返回 [0, 1] 。 示例 2 输入nums [3,2,4], target 6 输出[1,2] 示例 3 输入nums [3,3], target 6 输出[0,1]暴力解法classSolution{publicint[]twoSum(int[]nums,inttarget){intnnums.length;for(inti0;in;i){//1.避免重复使用同一个元素 2.避免重复计算同一对数for(intji1;jn;j){if(nums[i]nums[j]target){returnnewint[]{i,j};}}}/*等同于 int[] arr new int[2]; arr[0] i; arr[1] j; return arr;*/returnnewint[]{-1,-1};}}HashMap核心思想遍历当前元素时在 HashMap 中查找“我需要的另一个数”是否已经出现过如果出现过就直接返回答案否则把当前元素存起来。目标nums[i] nums[j] target如果当前数是 x那我需要找的另一个数是target - xHashMapInteger, IntegerKey(键)数组中某个数 Value值这个数的下标例如nums [2, 7, 11, 15]{2 - 0}importjava.util.HashMap;classSolution{publicint[]twoSum(int[]nums,inttarget){// 创建 HashMap// key - 数组中的值// value - 该值对应的下标HashMapInteger,IntegermapnewHashMap();// 一次遍历数组i 是当前元素的下标for(inti0;inums.length;i){// 当前遍历到的元素值intnumnums[i];// 计算还需要的那个数使得// num need targetintneedtarget-num;// containsKey判断 HashMap 中是否已经存在 need// 如果存在说明之前遍历过的某个数 当前数 targetif(map.containsKey(need)){// 通过 keyneed拿到它对应的下标intindexmap.get(need);returnnewint[]{index,i};}// 如果没找到需要的数// 把当前数和它的下标存入 HashMap// 供后续元素查找map.put(num,i);}returnnewint[0];}}2.字母异位词分组给你一个字符串数组请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 示例 1: 输入: strs [eat, tea, tan, ate, nat, bat] 输出: [[bat],[nat,tan],[ate,eat,tea]] 解释 在 strs 中没有字符串可以通过重新排列来形成 bat。 字符串 nat 和 tan 是字母异位词因为它们可以重新排列以形成彼此。 字符串 ate eat 和 tea 是字母异位词因为它们可以重新排列以形成彼此。 示例 2: 输入: strs [] 输出: [[]] 示例 3: 输入: strs [a] 输出: [[a]]思想找分类标准给每个字符串找一个标识只要两个字符串的标识一样它们就应该进同一组。classSolution{publicListListStringgroupAnagrams(String[]strs){MapString,ListStringmapnewHashMap();/*遍历 语法结构:for (元素类型 变量名 : 可迭代对象/数组) 不用下标直接一个个取元素。 */for(String str:strs){//字符串转换为字符数组char[]charsstr.toCharArry();Arrays.sort(chars);//排序后结果作为key 标识String keynewString(chars);//如果这个 key 还没有对应的列表就先创建if(!map.containsKey(key)){map.put(key,newArrayList())}map.get(key).add(str);}returnnewArrayList(map.values());}}3.最长连续序列给定一个未排序的整数数组 nums 找出数字连续的最长序列不要求序列元素在原数组中连续的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 1 输入nums [100,4,200,1,3,2] 输出4 解释最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。 示例 2 输入nums [0,3,7,2,5,8,4,6,0,1] 输出9 示例 3 输入nums [1,0,1,2] 输出3思想题目本质给你一个无序数组要你找最长的“值连续”的序列长度。不要求数组原位置连续。解法思路1把所有数组元素放入HashSet中。2遍历每个元素。3如果数组元素num - 1 不存在说明它是起点从这个起点开始不断查 num 1, num 2 …4统计这一段长度更新最大值。classSolution{publicintlongestConsecutive(int[]nums){// 1. 先把所有数字放进 HashSet方便 O(1) 查询同时自动去重HashSetIntegersetnewHashSet();for(int num:nums){set.add(num);}int maxLen0;// 2. 遍历集合中的每个数字for(int num:set){// 3. 只有当前数字是连续序列起点时才开始往后扩展if(!set.contains(num-1)){int currentNumnum;int currentLen1;// 4. 不断查找下一个连续数字while(set.contains(currentNum1)){currentNum;currentLen;}// 5. 更新最长长度maxLenMath.max(maxLen,currentLen);}}returnmaxLen;}}