【leetcode速通java版】05—— 快乐数、两数之和、四数相加II
【leetcode速通java版】05—— 快乐数、两数之和、四数相加II
前 言 🍉 作者简介：半旧518，长跑型选手，立志坚持写10年博客，专注于java后端 ☕专栏简介：代码随想录leetcode速通训练营java版本 🌰 文章简介：T202,T1
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;
}
}