有效的字母异位词
https://leetcode.cn/problems/valid-anagram/submissions/
【思路】
因为单词是由字母组成的，可以直接通过ASCII将字母看成是数字
public boolean isAnagram(String s, String t) { // 因为参数里面都是小写字母，因此只需要创建长度为26的数组即可 int[] arr = new int[26]; // 统计字符串1的每个字母的个数 for (int i = 0; i < s.length(); i++) { arr[s.charAt(i) - 'a'] += 1; } // 遍历字符串2，将相应的字母个数减少 for (int i = 0; i < t.length(); i++) { arr[t.charAt(i) - 'a'] -= 1; } // 如果有哪个字母的数量不为零，就足以说明两个字符串的字母个数不太相同 for (int num : arr) { if (num != 0) { return false; } } return true; }
- 时间复杂度: O(n)
- 空间复杂度: O(1)
两个数组的交集
使用Hash数组
可以用一个数组来记录元素的次数，但是如果数字的范围很大，就不建议使用这种方法了，因为会非常浪费内存
public int[] intersection(int[] nums1, int[] nums2) { int[] arr = new int[1001]; // 将nums1中有的元素的数量设置为1 for (int num1 : nums1) { if (arr[num1] == 0) { arr[num1]++; } } // 将 nums1和nums2 共有的数字数量设置为2，并记录数字为2的数量 int resultLen = 0; for (int num2 : nums2) { if (arr[num2] == 1) { arr[num2]++; resultLen++; } } // 将数字为2对应的下标拿出来存储到结果集合中 int[] result = new int[resultLen]; int i = 0; for (int j = 0; j < arr.length; j++) { if (arr[j] == 2) { result[i++] = j; } } return result; }
使用HashSet
直接使用HashSet来记录nums1的元素，然后遍历nums2，判断HashSet里面有没有即可，如果有的话，就添加到结果集中
public int[] intersection1(int[] nums1, int[] nums2) { HashSet<Integer> set = new HashSet<>(); HashSet<Integer> result = new HashSet<>(); for (int num1 : nums1) { set.add(num1); } for (int num2 : nums2) { if (set.contains(num2)) { result.add(num2); } } return result.stream().mapToInt(item -> item).toArray(); }
快乐数
https://leetcode.cn/problems/happy-number/
【思路】
该题主要是需要使用set来判断一个数字是否存在重复的情况，如果存在重复，那一定会陷入无限循环，直接返回false即可
public static boolean isHappy(int n) { // 用来存储总和，如果陷入无限循环，sum会重复 HashSet<Integer> sumSet = new HashSet<>(); while (true) { int sum = 0; while (n > 0) { // 取出末尾那个数字 int num = n % 10; sum += num * num; // 去掉末尾的数字 n = n / 10; } if (sum == 1) { return true; } else { if (sumSet.contains(sum)) { return false; } sumSet.add(sum); n = sum; } } }
两数之和
https://leetcode.cn/problems/two-sum/
【思路】
- 使用一个字典来存储已经遍历过的元素及其下标，等遍历到一个元素的时候，判断map中是否存在(target-元素)的键即可，如果存在，即可直接返回下标数组
- 因为下标没有顺序，直接用HashMap即可，如果有顺序的话，那就需要用LinkedHashMap
public int[] twoSum(int[] nums, int target) { HashMap<Integer, Integer> numAndIndexMap = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int num = nums[i]; if (numAndIndexMap.containsKey(target - num)) { return new int[]{i, numAndIndexMap.get(target - num)}; } else { numAndIndexMap.put(num, i); } } return null; }
四数相加
https://leetcode.cn/problems/4sum-ii/
【思路】
- 如果直接使用四层循环，时间复杂度太高了，可以使用HashMap来存储(num1+num2)及其数量
- 在使用两层循环遍历nums3、nums4，使用一个count来实时记录数量即可，num+=map.get(0-num3-num4)
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { HashMap<Integer, Integer> sumOfNum1Num2AndNumberMap = new HashMap<>(); for (int num1 : nums1) { for (int num2 : nums2) { int sum = num1 + num2; if (!sumOfNum1Num2AndNumberMap.containsKey(sum)) { sumOfNum1Num2AndNumberMap.put(sum, 1); } else { sumOfNum1Num2AndNumberMap.put(sum, sumOfNum1Num2AndNumberMap.get(sum) + 1); } } } int count = 0; for (int num3 : nums3) { for (int num4 : nums4) { if (sumOfNum1Num2AndNumberMap.containsKey(0 - num3 - num4)) { count += sumOfNum1Num2AndNumberMap.get(0 - num3 - num4); } } } return count; }
赎金信
https://leetcode.cn/problems/ransom-note/
【思路】
这道题很容就想到使用map来存储magazine的字符及其数量，但是很容易漏掉一个细节，那就是单词都是由小写字母组成的，这时使用一个长度为26的数组来存储数量会更加好，因为使用map的空间消耗比数组更大，因为map要维护红黑树或哈希表，还需要做哈希函数
【使用map实现】
public boolean canConstruct(String ransomNote, String magazine) { HashMap<Character, Integer> map = new HashMap<>(); for (int i = 0; i < magazine.length(); i++) { char c = magazine.charAt(i); if (!map.containsKey(c)) { map.put(c, 1); } else { map.put(c, map.get(c) + 1); } } for (int i = 0; i < ransomNote.length(); i++) { char c = ransomNote.charAt(i); if (map.containsKey(c)) { Integer num = map.get(c); if (num == 1) { map.remove(c); } else { map.put(c, map.get(c) - 1); } } else { return false; } } return true; }
【使用数组来实现】
public boolean canConstruct1(String ransomNote, String magazine) { int[] arr = new int[26]; for (int i = 0; i < magazine.length(); i++) { char c = magazine.charAt(i); arr[c - 'a']++; } for (int i = 0; i < ransomNote.length(); i++) { char c = ransomNote.charAt(i); if (arr[c - 'a'] > 0) { arr[c - 'a']--; } else { return false; } } return true; }
三数之和
https://leetcode.cn/problems/3sum/description/
【双指针法】
- 先升序排序
- 然后写一个循环来遍历数组的前 n-2 个元素来作为三元组的第一个元素，第二、第三个元素使用双指针方法来同时寻找出来，这样算法整体的时间复杂度是O(n^2)
- 该题的关键是如何去重，只要三元组里面的元素都一样，无论顺序怎么样都算是重复
public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> result=new ArrayList(); // 升序排序 Arrays.sort(nums); int left,right; for(int i=0;i<nums.length-2;i++){ // 如果第一个元素都已经大于0，因为数组是递增顺序的，肯定没有对应的三元组 if (nums[i] > 0) { return result; } // 对三元组中的第一个元素进行去重 if (i > 0 && nums[i] == nums[i - 1]) { continue; } left=i+1; right=nums.length-1; while(left<right){ if(nums[i]+nums[left]+nums[right]>0){ right--; }else if(nums[i]+nums[left]+nums[right]<0){ left++; }else{ List<Integer> group=new ArrayList(); group.add(nums[i]); group.add(nums[left]); group.add(nums[right]); result.add(group); // 对第三个元素进行去重 while (right > left && nums[right] == nums[right - 1]) right--; // 对第二个元素进行去重 while (right > left && nums[left] == nums[left + 1]) left++; right--; left++; } } } return result; }
四数之和
https://leetcode.cn/problems/4sum/description/
【说明】
该题还是可以使用双指针法，其实和三数之和类似的，三数之后是遍历第一个元素，然后双指针处理后面两个元素；四数之和就是遍历前两个元素，双指针处理后面两个元素。如果有五数之和、六数之和，也是类似的方法，多遍历前面的元素而已。因此双指针法只是比暴力遍历求解少了一层遍历，即将时间复杂度从O(n)变为O(n-1)
public static List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> result = new ArrayList<>(); Arrays.sort(nums); for (int i = 0; i < nums.length - 3; i++) { // nums[i]必须要大于0，不然当nums是{1, -2, -5, -4, -3, 3, 3, 5}，target是-11，就会不满足 if (nums[i] > 0 && nums[i] > target) { return result; } if (i > 0 && nums[i] == nums[i - 1]) { // 去重 continue; } for (int j = i + 1; j < nums.length - 2; j++) { // 不加j > i + 1的话，nums=[-2,-1,-1,1,1,2,2], target=0这个案例会出现问题 if (j > i + 1 && nums[j] == nums[j - 1]) { // 去重 continue; } int left = j + 1; int right = nums.length - 1; while (left < right) { int sum = nums[i] + nums[j] + nums[left] + nums[right]; if (sum > target) { right--; } else if (sum < target) { left++; } else { result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right])); while (left < right && nums[left + 1] == nums[left]) { left++; } while (left < right && nums[right - 1] == nums[right]) { right--; } right--; left++; } } } } return result; }
