T202 快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 True ；不是，则返回 False 。
思路：这道题目中出现了无限循环的判断，符合哈希表的应用条件，即：快速判断某个元素是否会重复出现。
class Solution { public boolean isHappy(int n) { // 解法1 哈希表 // 1.维护一个哈希表 Set<Integer> set = new HashSet<Integer>(); // 2.循环,判断这个数是否为1或者出现了重复数 while(n != 1 && !set.contains(n)) { set.add(n); n = getNextNumber(n); } // 3.返回，通过判断n是否为1判断是否为快乐数 return n == 1; } private int getNextNumber(int n) { int result = 0; while(n > 0) { int temp = n % 10; result += temp * temp; n = n / 10; } return result; } }
T1.两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
思路：
1.两层循环暴力求解
class Solution { public int[] twoSum(int[] nums, int target) { for(int i = 0; i < nums.length; i++) { // 外循环，控制轮次 for(int j = i+1; j < nums.length; j++) { // 内循环，遍历查找 if(target == nums[i] + nums[j]) { return new int[]{i,j}; } } } return new int[0]; } }
方法2：哈希表
这里表面上需要找配对的两个元素，实际上，定1找1.比如target是9，第一个元素是2，就只需要找到7就可以了。
因此本题符合哈希表的使用条件：快速判断某个元素是否出现过，或者在一个集合里。
可以用一个集合来维护哈希列表，因为需要记录元素的位置、还需要记录元素的值的大小，因此使用key-value键值对存储。使用map构建哈希表。
class Solution { public int[] twoSum(int[] nums, int target) { // 传参中出现了数组，因此需要对数组执行临界指判断 int[] res = new int[2]; if(nums == null || nums.length == 0) { return res; } // key-value：值-位置 Map<Integer, Integer> map = new HashMap<>(); for(int i = 0; i < nums.length; i++) { // 外循环，控制轮次 int temp = target - nums[i]; if(map.containsKey(temp)) { res[0] = i; res[1] = map.get(temp); break; // 目标达成，终止循环 } map.put(nums[i], i); } return res; } }
T454 四数相加II
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。
分析： 需要快速判断某个元素(0)是否在集合(四数之和)里，使用哈希表解题.
考虑到四数相加问题太过于复杂，将其通过拆分为两两数一对求解。
同上一题思路一致，需要存储值以及频次，因此使用map求解问题。
class Solution { public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { // 哈希表：需要快速判断某个元素(0)是否在集合(四数之和)里 // todo:临界判断 int temp = 0; int res = 0; Map<Integer, Integer> map = new HashMap<>(); for(int i : nums1) { for(int j : nums2) { temp = i +j; if(map.containsKey(temp)) { map.put(temp, map.get(temp) + 1); //不要用x++ } else { map.put(temp, 1); } } } for(int i : nums3) { for(int j : nums4) { temp = i +j; if(map.containsKey(0 - temp)) { res += map.get(0 - temp); //重点关注 } } } return res; } }
