LeetCodeHot100

1.两数之和

解题思路：

1.暴力解法 两个for循环解决问题 时间复杂度为 O(n2)

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];}
}

2.哈希表

使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1)。

这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

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

2.字母异位词分组

解题思路：字母相同，但排列不同的字符串，排序后都一定是相同的。因为每种字母的个数都是相同的，那么排序后的字符串就一定是相同的。

import java.util.*;public class groupAnagrams {public static void main(String[] args) {String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};List<List<String>> list= groupAnagrams(strs);list.forEach(System.out::println);}public static List<List<String>> groupAnagrams(String[] strs) {//用map，key存储排序的后的字符串，value就是对应的字符串集合Map<String, List<String>> map = new HashMap<>();//遍历strsfor (String str : strs) {//讲字符串转为char数组char[] chars = str.toCharArray();//对字符串进行排序Arrays.sort(chars);//构建排序后的字符串String key = new String(chars);//如果map中存在key对应的list，返回该list集合，如果不存在，返回一个新的list集合List<String> list = map.getOrDefault(key, new ArrayList<String>());list.add(str);//将key和value存入mapmap.put(key, list);}//讲map转为List进行返回return new ArrayList<List<String>>(map.values());}
}

3.最长连续序列

解题思路：把输入放入map中，然后遍历判断。难点其实是要求时间复杂度为0.这里遍历的时候就需要做判断，只有当一个数是连续序列的第一个数是才进入内存循环

package CodeThink;import java.util.HashSet;
import java.util.Set;public class longestConsecutive {public static void main(String[] args) {int[] nums = {100,4,200,1,3,2};int res = longestConsecutive(nums);System.out.println(res);}public static int longestConsecutive(int[] nums) {Set<Integer> sets = new HashSet<>();for (int num : nums) {sets.add(num);}int max = 0;for (int set : sets) {if(!sets.contains(set-1)){int temp = 0;while(sets.contains(set)) {temp++;set++;}max = Math.max(max, temp);}}return max;}
}