yub‘s Algorithmic Adventures_Day9
两数之和
思路分析
看到题目描述首先想到用两层for循环解决问题.
分别从i位置和j(i+1)位置开始相加遍历判断.
注意不越界条件
数组
class Solution {
public int[] twoSum(int[] nums, int target) {
//我们要找到2个数之和等于target
//即我们需要找到nums[i] + nums[j] == target，并且返回他们的下标（i和j），其中i != j
int[] 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的作用
class Solution {
public int[] twoSum(int[] nums, int target) {
//创建最终输出的数组
int[] res = new int[2];
//排除特殊情况
if(nums == null || nums.length == 0) {
return res;
}
//创建需要的Map
Map<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对应的value
map.put(nums[i],i);
}
return res;
}
}
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
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
//首先创建需要的Map
Map<Integer, Integer> map = new HashMap<>();
//创建sum和res
int 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为1
map.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 ，则返回设置的默认值。
hashmap.getOrDefault(Object key, V defaultValue)
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;
}
}
原文地址：https://blog.csdn.net/weixin_72981769/article/details/142913112
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！