LeetCode Hot100（持续更新中）

一、哈希

（一）两数之和

思路一：传统方法-双层循环遍历
时间复杂度：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());
    }
}