242. 有效的字母異位詞

題目鏈接：242. 有效的字母異位詞

思路：哈希法。利用數組來記錄出現的字母個數，然后判斷是否為字母異位詞。

時間復雜度：O(n)

class Solution {public boolean isAnagram(String s, String t) {int[] count = new int[26];for (int i = 0; i < s.length(); i++) {// 并不需要記住字符a的ASCII，只要求出一個相對數值就可以了count[s.charAt(i) - 'a']++;}for (int i = 0; i < t.length(); i++) {count[t.charAt(i) - 'a']--;}for (int i : count) {// record數組如果有的元素不為零0，// 說明字符串s和t一定是誰多了字符或者誰少了字符。if (i != 0) {return false;}}// record數組所有元素都為零0，說明字符串s和t是字母異位詞return true;}
}

---

349. 兩個數組的交集

題目鏈接：349. 兩個數組的交集

思路：哈希法。利用HashSet集合來判斷元素是否存在，set集合判斷元素是否存在的時間復雜度為O(1)。注意，這里涉及將集合轉換為int數組的操作。

時間復雜度：O(n)

class Solution {public int[] intersection(int[] nums1, int[] nums2) {// 存入set，然后遍歷setSet<Integer> set1 = new HashSet<>();Set<Integer> result = new HashSet<>();for (int num : nums1) {set1.add(num);}for (int num : nums2) {if (set1.contains(num)) {result.add(num);}}// 將結果集合轉為數組// return result.stream().mapToInt(x -> x).toArray();int[] res = new int[result.size()];int i = 0;for(int num : result){res[i] = num;i++;}return res;}
}

---

202. 快樂數

題目鏈接：202. 快樂數

思路：哈希法加數值各個位上的單數操作，使用HashSet集合來檢測是否循環。

時間復雜度：里面while循環的時間復雜度為O(logn)，因為數字的位數由logn決定。

class Solution {public boolean isHappy(int n) {Set<Integer> set = new HashSet<>();int sum = 0;while (n != 1) {// 取數值各個位上的單數平方之和while (n != 0) {sum += Math.pow(n % 10, 2);n = n / 10;}// 如果這個sum曾經出現過，說明已經陷入了無限循環了if (set.contains(sum)) {return false;}set.add(sum);n = sum;sum = 0;}return true;}
}

---

1. 兩數之和

題目鏈接：1. 兩數之和

思路：哈希法，使用HashMap集合key存放元素value存放下標，遍歷一遍數組，判斷Map集合中是否有符合條件的元素，如果有，返回兩個元素的下標，每次判斷結束要將當前元素值和下標存放進Map集合。注意，為了防止當前元素也是符合條件的元素（即兩個當前元素相加為目標值）導致的兩個下標相同，所以要在判斷結束之后再將當前元素和下標放進Map集合。

時間復雜度：O(n)

class Solution {public int[] twoSum(int[] nums, int target) {// 維護 val -> index 的映射HashMap<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {// 查表，看看是否有能和 nums[i] 湊出 target 的元素int need = target - nums[i];if (map.containsKey(need)) {return new int[]{map.get(need), i};}// 存入 val -> index 的映射map.put(nums[i], i);}return null;}
}

---