四数相加II & 赎金信 & 三数之和 & 四数之和
2024-09-08 18:23:57
一、四数相加Ⅱ
1.方法概述
- 首先定义一个map，key放a和b两数之和，value 放a和b两数之和出现的次数。遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中。定义int变量count，用来统计 a+b+c+d = 0 出现的次数。在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。最后返回统计值 count 就可以了。
2、具体实现
Java实现
点击查看代码
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Map<Integer,Integer> map = new HashMap<>();
int tmp;
int ret = 0;
for(int i:nums1){
for(int j:nums2){
tmp = i+j;
if(map.containsKey(tmp)){
map.put(tmp,map.get(tmp)+1);
}else{
map.put(tmp,1);
}
}
}
for(int i:nums3){
for(int j:nums4){
tmp = i+j;
if(map.containsKey(0-tmp)){
ret += map.get(0-tmp);
}
}
}
return ret;
}
}
3.要点总结
- 因为本题即涉及到目标值又涉及到次数的统计，可以考虑使用map来解决。map的key来存放值，value来存放出现的次数。
- 本题是四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑有重复的四个元素相加等于0的情况。
- 两两数组匹配寻找在时间效率上更优。
二、救赎金
1.方法概述
- 本题判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成，首先创建一个大小为26的数组来记录，字母出现的位置和次数。使用增强for和toCharArray()来遍历字符串，第一个字符串字母-'a'存入数组所对应的下标对应值+1用来记录出现次数.第二个字符串字母-'a'对应的下标对应值-1。最后遍历数组中是否含有<0的情况即可。
2.具体实现
Java实现
点击查看代码
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] arr = new int[26];
for(char c : magazine.toCharArray()){
arr[c-'a'] +=1;
}
for(char c:ransomNote.toCharArray()){
arr[c-'a'] -=1;
}
for(int i:arr){
if(i<0){
return false;
}
}
return true;
}
}
3.要点总结
- 因为题目所只有小写字母，那可以采用空间换取时间的哈希策略，用一个长度为26的数组还记录magazine里字母出现的次数。然后再用ransomNote去验证这个数组是否包含了ransomNote所需要的所有字母。
- toCharArray() 方法将字符串转换为字符数组。
三、三数之和
1.方法概述
- 引用解法。首先将给定整数数组进行排序，使其从小到大依次排列。然后最外层使用for循环，i从下标0开始，同时定义一个位置在i+1上的left下标，定义一个在数组末尾位置上的right下标。在数组中查找a(nums[i])+b(nums[left])+c(nums[right])=0。当a+b+c>0,说明三数之和大了，需要right下标向左移动，如果a+b+c<0则需要left向右移动。当a+b+c=0时将元素值存放到二维数组ret中。因为该题需要不重复的三元组（组里面的元素可以重复），接下来就是a，b，c的去重操作。首先是a的去重，因为首先是在第一个元素确定的情况下查找的剩下两个元素，如果当第一个元素重复时就说明这样的情况已近存在，需要去重。同理接下来就是b，c的去重。最后返回ret。
2.具体实现
Java实现
点击查看代码
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ret = new ArrayList<>();
Arrays.sort(nums);
for(int i = 0;i<nums.length;i++){
if(nums[i] > 0){
return ret;
}
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{
ret.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 ret;
}
}
3.要点总结
- 首先将数组进行排序，本题原数组元素和下标对本题的解决无影响，可以先进行排序，方便后面的查找遍历以及去重操作。
- 本题的难点在于三元组不重复，在查找目标元素时需要去重操作。去重操作的核心就是判断三元组的第一个元素是否在它之前出现过，如果出现过，则证明该元素已近遍历过，在遍历同样的元素，必定导致重复三元组的出现。
- 在for循环这层遍历中，left和right需要不停的遍历寻找匹配元素，同时也需要去重操作，去重的思想和a的去重思想是一致。判断下一个元素是否和上一个出现元素相同，不同点是一个是从i+1下标开始遍历，另一个是从数组末端下标开始遍历。如果大了，说明right需要左移，如果小了，说明left需要右移，否则存入到二维数组中去，直到相遇，停止while层循环（因为题设要求满足i != left != right)，进入下一次for循环。
- 还有一个关键点是b，c的去重要建立在存在一个三元组之后，否则就都会被去掉。
- 当b,c去重以后指针实际指向与第二位b（与第三位c）相同的数，因此指针需要移动指向不同的数,因此还需要left++，right--；
四、四数之和
1.方法概述
- 总体思想和三数之和一样，只是需要在最外层再套一个for循环来确定一个元素。
2.具体实现
Java实现
点击查看代码
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> ret = new ArrayList<>();
Arrays.sort(nums);
for(int i = 0;i < nums.length;i++){
if(nums[i]>0 && nums[i]>target){
return ret;
}
if(i>0 && nums[i-1] == nums[i]){
continue;
}
for(int j = i+1;j<nums.length;j++){
if(j > i+1 && nums[j-1] == nums[j]){
continue;
}
int left = j+1;
int right = nums.length-1;
while(left<right){
long sum = (long)nums[i]+nums[j]+nums[left]+nums[right];
if(sum > target){
right--;
}else if(sum < target){
left++;
}else{
ret.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
while(left < right && nums[right] == nums[right-1]){
right--;
}
while(left < right && nums[left] == nums[left+1]){
left++;
}
left++;
right--;
}
}
}
}
return ret;
}
}
3.要点总结
- 不要判断nums[k] > target 就返回了，三数之和 可以通过 nums[i] > 0 就返回了，因为 0 已经是确定的数了，四数之和这道题目 target是任意值。比如：数组是[-4, -3, -2, -1]，target是-10，不能因为-4 > -10而跳过。但是我们依旧可以去做剪枝，逻辑变成nums[i] > target && (nums[i] >=0 || target >= 0)就可以了。
- 因为只要 nums[k] + nums[i] > target，那么 nums[i] 后面的数都是正数的话，就一定不符合条件了。
最新文章
- Java学习之路：不走弯路，就是捷径
- html前端总结
- C#读写app.config中的数据
- caffe中添加local层
- ELK日志管理之——logstash部署
- jq 操作table
- [Android Pro] 超能RecyclerView组件使用
- 标准化css属性顺序
- linux 查看系统信息命令
- 算法题C#
- github 更新fork分支
- C#基础知识-基本的流程控制语句（三）
- 201521123087《Java程序设计》第14周学习总结
- ORACLE使用数据泵导入导出部分表
- CPP--正码，反码，补码~附整数溢出的探讨
- 反射demo(拷贝一个对象)
- 6.04-news_xpath3
- 【SRM-06 D】五色战队&&【codeforces 788E】 New task
- CentOS 6.8 部署django项目二
- JSP页面嵌套乱码解决