刷题笔记:LeetCode15-经典三数和的Hash写法
三数和旧题新作Hash法(Java)
先上题目。
1.题目描述
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。
注意: 答案中不可以包含重复的三元组。
示例:
给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为: [ [-1, 0, 1], [-1, -1, 2] ]
2.解题思路
传统双指针解法这里不再赘述,其时间复杂度为O(N^2)。
对于由两数和演变的三数和,用hash法解(两层for循环就可以确定 a 和b 的数值了,可以使用哈希法来确定 0-(a+b) 是否在 数组里出现过->时间复杂度也为O(N^2))思路更为直观。
先回顾两数和
3.回顾两数和-LeetCode-1的Hash法
3.1题目描述
给定一个整数数组 nums
和一个整数目标值 target
,请你在该数组中找出 和为目标值 target
的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
3.2 Hash法解两数和
import java.util.HashMap;
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer,Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if(map.containsKey(target - nums[i])){
int[] res = {map.get(target - nums[i]),i};
return res;
}
map.put(nums[i], i);
}
return null;
}
}
两数和只需O(N),维护一个map,key用来存储nums[i],value用来存储index,也就是i。遍历nums,如果当前target - nums[i]在map中,就直接返回i和target-nums[i]的下标。否则将(nums[i],i)加入map。
4.回到三数和
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
// public class F15{
// public static void main(String[] args) {
// int[] nums = {-1,0,1,2,-1,-4};
// List<List<Integer>> res = new Solution().threeSum(nums);
// }
// }
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
HashSet<MyList> result = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
if(nums[i] > 0){
break;
}
if(i > 0 && nums[i] == nums[i - 1]){
continue;
}//a为最小值
HashSet<Integer> cSet = new HashSet<>();
for (int j = i + 1; j < nums.length; j++) {
if(cSet.contains(0-nums[i]-nums[j])){
MyList temp = new MyList(nums[i], nums[j], 0-nums[i]-nums[j]);
result.add(temp);
}else{
cSet.add(nums[j]);
}
}
}
List<List<Integer>> res = new ArrayList<>();
for (MyList o: result) {
res.add(o);
}
return res;
}
class MyList extends ArrayList<Integer>{
public MyList(int a,int b, int c){
this.add(a);
this.add(b);
this.add(c);
}
@Override
public boolean equals(Object o) {
@SuppressWarnings("all")
ArrayList<Integer> obj = (ArrayList<Integer>)o;
HashMap<Integer,Integer> mapObj = new HashMap<>();
for (Integer integer : obj) {
if(mapObj.containsKey(integer)){
mapObj.put(integer,mapObj.get(integer)+1);
}else{
mapObj.put(integer, 1);
}
}
HashMap<Integer,Integer> mapThis = new HashMap<>();
for (Integer integer : this) {
if(mapThis.containsKey(integer)){
mapThis.put(integer,mapThis.get(integer)+1);
}else{
mapThis.put(integer, 1);
}
}
Set<Integer> setObj = mapObj.keySet();
for (Integer integer : setObj) {
if(!mapThis.containsKey(integer)){
return false;
}
if(mapObj.get(integer)!=mapThis.get(integer)){
return false;
}
}
return true;
}
}
}
4.1方法idea
1.是对nums进行排序,则第一层循环的a = nums[i]就是所选三数的最小值,则nums[i]必小于0;
2.对于连续nums[i]的过滤,完成了对于nums[i]的去重;
3.b = nums[j]其实为最大值,因为是遍历过的b,比如今的b要小;
4.网上对于b,c的去重剪枝有其他描述,实在不好理解(也可能是因为我太菜),如下c++的一段代码(comes from 代码随想录 (programmercarl.com))。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
// 找出a + b + c = 0
// a = nums[i], b = nums[j], c = -(a + b)
for (int i = 0; i < nums.size(); i++) {
// 排序之后如果第一个元素已经大于零,那么不可能凑成三元组
if (nums[i] > 0) {
break;
}
if (i > 0 && nums[i] == nums[i - 1]) { //三元组元素a去重
continue;
}
unordered_set<int> set;
for (int j = i + 1; j < nums.size(); j++) {
if (j > i + 2
&& nums[j] == nums[j-1]
&& nums[j-1] == nums[j-2]) { // 三元组元素b去重
continue;
}
int c = 0 - (nums[i] + nums[j]);
if (set.find(c) != set.end()) {
result.push_back({nums[i], nums[j], c});
set.erase(c);// 三元组元素c去重
} else {
set.insert(nums[j]);
}
}
}
return result;
}
};
5.(!!!重点)故而我就借助了Java的Collection容器特性,重写了ArrayList的equals方法(由于LeetCode的提交机制,我将class MyList extends ArrayList<Integer>写成了成员内部类)。
要了解重写的原因得要了解Java的HashSet底层实现机制——HashSet底层相当于HashMap用常数填充了value只留下了key。对于HashSet而言,不允许出现重复元素。其判断是否是重复元素的标准实在加入时先判断对象地址(hashCode)不一样则判断为不重复;否则,再调用对象的equals方法跟hashCode相同的对象比较。
简单来说,就是只要重写了ArrayList的equals方法,改变判等规则为所有元素及其个数一致,即为相等——则满足题意。HashSet的add方法就会自动帮我们去重啦!
原文地址:https://blog.csdn.net/m0_53190754/article/details/136078490
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!