数据结构刷题（七）：202快乐数、1两数之和、454四数相加II、15三数之和、18四树之和

1.快乐数

题目链接

思路：使用set，当set中出现相同元素时，返回false

注意：while循环中语句顺序； 除数取余。

解法：

public boolean isHappy(int n){Set<Integer> res = new HashSet<>();int[] arr = new int[26];while (n != 1 && !res.contains(n)){// 注意下面两句的顺序  若顺序颠倒，res添加完n后立马while循环终止，原因是先执行chu(n)，n未变res.add(n);n = chu(n);}return n == 1;
}public int chu(int n){int sum = 0;while (n != 0){int t = n % 10;sum += t * t;n /= 10;}return sum;
}

2.两数之和

题目链接

思路：使用map， 采用k-v来存，k存储值，v存储索引

注意：四个问题需想清楚？

• 为什么会想到用哈希表？

答：这里需要集合来存放我们遍历过的元素，然后在遍历数组的时候去询问这个集合某元素是否遍历过，也就是在询问该元素是否出现在这个集合，立马想到哈希表

• 哈希表为什么用map？

答：不仅要知道元素有没有遍历过，还有知道这个元素对应的下标，需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适。

• 本题map是用来存什么的？

答：map目的用来存放我们访问过的元素，因为遍历数组的时候，需要记录我们之前遍历过哪些元素和对应的下标，这样才能找到与当前元素相匹配的

• map中的key和value用来存什么的？

答：{key：数据元素，value：数组元素对应的下标}

解法：

public int[] twoSum(int[] arr, int n) {Map<Integer, Integer> map = new HashMap<>();int[] res = new int[2];if (arr.length == 0 || arr == null)return res;for (int i = 0; i < arr.length; i++) {int temp;temp = n - arr[i];if (map.containsKey(temp)){res[1] = i;res[0] = map.get(temp);}map.put(arr[i], i);}return res;
}

3.四数相加II

题目链接

思路：使用map，k存储值，v存储每个值出现的次数

注意：注意for的格式，区分i是具体值还是索引值

解法：

public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4){Map<Integer, Integer> map = new HashMap<>();int sum = 0;for (int i : nums1) {for (int i1 : nums2) {int t = i + i1;if (map.containsKey(t))map.put(t, map.get(t) + 1);elsemap.put(t, 1);}}for (int i : nums3) {for (int i1 : nums4) {int t = i + i1;if (map.containsKey(0 - t))sum += map.get(0 - t);}}return sum;}

4.三数之和

题目链接

思路：排序+相向双指针法；看似三指针， i、left(i+1出发)、right(最后一位出发)

注意：注意将a+b+c=0中的a、b、c都要做去重操作，尤其是a的去重条件更为严苛

解法：

public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> result = new ArrayList<>();// 排序Arrays.sort(nums);// 看似三指针，   i、left(i+1出发)、right(最后一位出发)for (int i = 0; i < nums.length; i++) {// 当排序后的，相加第一位都>0时必然整个相加都＞0if (nums[i] > 0){return result;}// 如果重复了怎么办，nums[i]是nums里遍历的元素，那么应该直接跳过去。if (i > 0 && nums[i] == nums[i - 1]){continue;}int left = i + 1;int right = nums.length - 1;while (right > left){int sum = nums[i] + nums[left] + nums[right];if (sum > 0){right--;}else if (sum < 0){left++;}else {result.add(Arrays.asList(nums[i], nums[left], nums[right]));while (right > left && nums[right] == nums[right - 1]) right--;while (right > left && nums[left] == nums[left + 1]) left++;right--;left++;}}}return result;
}

5.四树之和

题目链接

思路：同三数之和，排序+双指针法；比三数之和需多加一个for循环

注意：三数之和是与0比较，这个题是与target比较； 当排序后的，相加第一位都>0且target<第一位进行判断

解法：

public List<List<Integer>> fourSum(int[] nums, int target){List<List<Integer>> result = new ArrayList<>();Arrays.sort(nums);for (int i = 0; i < nums.length; i++) {if (nums[i] > 0 && target < nums[i])    //区别三数之和的这一判断条件return result;if (i > 0 && nums[i] == nums[i - 1]){  // 对nums[i]去重continue;}for (int j = i + 1; j < nums.length; j++){if (j > i + 1 && nums[j] == nums[j - 1]) // 对nums[j]去重{continue;}int l = j + 1;int r = nums.length - 1;while (r > l){int sum = nums[i] + nums[j] + nums[l] + nums[r];if (sum > target)r--;else if (sum < target)l++;else{result.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));while (r > l && nums[l] == nums[l + 1])l++;while (r > l && nums[r] == nums[r - 1])r--;l++;r--;}}}}return result;
}