yub‘s Algorithmic Adventures

两数之和

link：1. 两数之和 - 力扣（LeetCode）

思路分析

看到题目描述首先想到用两层for循环解决问题.
分别从i位置和j(i+1)位置开始相加遍历判断.
注意不越界条件

数组

java">class Solution {public int[] twoSum(int[] nums, int target) {//我们要找到2个数之和等于target//即我们需要找到nums[i] + nums[j] == target，并且返回他们的下标（i和j），其中i != jint[] ans = new int[2]; //声明一个大小为2的数组用来保存结果//我们通过循环来遍历所有的数字int n = nums.length;  //用一个变量n保存nums的长度//i为第一个数的下标，nums一共有n个数，所以i的取值范围是[0, n-1]for(int i = 0; i < n; i++){//j为第二个数的下标。for(int j = i + 1; j < n; j++){//对于每个数nums[i]，我们验证一遍其他数（nums[j]）跟它的和是否等于target//如果满足条件if(nums[i] + nums[j] == target){//将下标写入返回值数组里ans[0] = i;ans[1] = j;//返回return ans;}}}//默认返回值return new int[0];}
}

HashMap

Tips
当我们查询一个元素是否出现过或者一个元素是否在集合里时，首先要想到哈希法.

之前了解到哈希数组的运用是受到大小的限制，如果元素过少会浪费内存空间.
set是一个集合，存储的元素只能是一个key.本题不仅要判断y是否存在还要记录y的位置，不适用.

我们需要一个集合存储我们遍历的元素，对应的key值和value值分别存放元素和下标.(HasMap)

map的作用

java">class Solution {public int[] twoSum(int[] nums, int target) {//创建最终输出的数组int[] res = new int[2];//排除特殊情况if(nums == null || nums.length == 0) {return res;}//创建需要的MapMap<Integer,Integer> map = new HashMap<>();for(int i = 0;i < nums.length; i++) {int tmp = target - nums[i];if(map.containsKey(tmp)) {res[1] = i;res[0] = map.get(tmp);}//获取key对应的valuemap.put(nums[i],i);}  return res;}
}

java">hashmap.get(Object key)
//get方法获取指定key的value
hashmap.put（K key，V value）
//将键值对添加到HashMap中

四数之和

link：454. 四数相加 II - 力扣（LeetCode）

思路分析

首先看到四数加和，很容易想到两两分组遍历分别求和.利用map中key和value分别存储两个数组元素之和以及出现的次数（value）最后利用两两打足求和之后加法原则a+b（A）+ c+d（B）= 0，0 - B = A，如果A在map中出现过，就用定义的计数器count吧map中key对应的value统计出来最后返回count即可.【出现过几次就有几组】

HashMap

java">class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {//首先创建需要的MapMap<Integer, Integer> map = new HashMap<>();//创建sum和resint sum,res = 0;//求a、b(A)数组之和for(int i : nums1) {for(int j : nums2){sum = i + j;//如果tmp已经在map中存储过 value+1更新存储//put存储键值对 get获取value值if(map.containsKey(sum)) {map.put(sum,map.get(sum) + 1);}else {//第一次出现在map中value为1map.put(sum,1);}}}//求c、d(B)两数组之和并根据逻辑公式检查A数组中是否存在对应数值for(int i : nums3) {for(int j : nums4){sum = i + j;if(map.containsKey(0 - sum)) {res += map.get(0 - sum);}}}return res;}
}

补充getOrDefault()

getOrDefault() 方法获取指定 key 对应对 value，如果找不到 key ，则返回设置的默认值。

java">hashmap.getOrDefault(Object key, V defaultValue)

java">class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {Map<Integer,Integer> map = new HashMap<>();int res = 0;int sum = 0;for(int i:nums1){for(int j:nums2){sum = i+j;map.put(sum,map.getOrDefault(sum,0)+1);}}for(int i:nums3){for(int j :nums4){sum = i + j;res+=map.getOrDefault(0-sum,0);}}return res;}
}