一、哈希

（一）两数之和

思路一：传统方法-双层循环遍历
时间复杂度：O(n^2)

空间复杂度：O(1)

class Solution {public int[] twoSum(int[] nums, int target) {// 两层循环求解 时间复杂度O(N^2) 空间复杂度O(1)int[] goal = new int[2];for (int i = 0; i < nums.length - 1; i++) {for (int j = i+1; j < nums.length; j++) {if ( (nums[i] + nums[j]) == target ) {goal[0] = i;goal[1] = j;return goal;}}}throw new IllegalArgumentException("no such two nums.");}
}

思路二：HashMap方法-一次遍历
时间复杂度：O(n)

空间复杂度：O(n)

class Solution {public int[] twoSum(int[] nums, int target) {// HashMap求解 时间复杂度O(N) 空间复杂度O(N)Map<Integer, Integer> numsMap = new HashMap();numsMap.put(nums[0], 0);for (int i = 1; i < nums.length; i++) {// 计算当前值距离目标值的补数int complement = target - nums[i];// 查看当前补数是否存在numsMap中if (numsMap.containsKey(complement)) {return new int[] { numsMap.get(complement), i};}// 不存在，将当前值加入numsMap中numsMap.put(nums[i], i);}throw new IllegalArgumentException("未找到符合要求的两个下标");}
}

（二）字母异位词分组

思路：采用哈希+排序

时间复杂度：O(N*M log M)  N为字符串数组长度，M为字符串长度

空间复杂度：O(N*M)

class Solution {public List<List<String>> groupAnagrams(String[] strs) {// 字母异位词分组// 时间复杂度 O(N*MlogM)  N为字符串数组长度，M为字符串长度// 空间复杂度 O(N*M) // 创建一个HashMap，键存储排序后的字符串，值存储字母异位词Map<String, List<String>> anagramMap = new HashMap<>();// 遍历字符串数组for (String str : strs) {// 对字符串重新进行排序char[] chars = str.toCharArray();Arrays.sort(chars);String sortedStr = new String(chars);// 如果哈希表不存在该字符串，则添加if ( !anagramMap.containsKey(sortedStr) ) {// 哈希表新增anagramMap.put(sortedStr, new ArrayList<>());}// 哈希表value赋值anagramMap.get(sortedStr).add(str);}return new ArrayList<>(anagramMap.values());}
}