链接
https://programmercarl.com/0454.%E5%9B%9B%E6%95%B0%E7%9B%B8%E5%8A%A0II.html
454.四数相加II
题目
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
0 <= i, j, k, l < nnums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
输入:
- A = [ 1, 2]
- B = [-2,-1]
- C = [-1, 2]
- D = [ 0, 2]
输出: 2
思路
- 初步思路
- 选数据结构，数据量不大，但是数组有4个，选择数组。
- 终止条件，固定数组1，遍历2，遍历3，遍历4，四层for循环，直到四个数相加等于0时，返回元素位置，键和值，选择map比较好
- 代码随想录思路
-
4个数组
- 前两个数组遍历一遍，计算a+b的值(key)和次数(value)
- 后两个数组进行【查询】操作，查询是否有-(c+d)=(a+b)的情况，如果有，count+value(注意为什么加而不是乘)
-
class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int res=0;//存储和为0的元组Map<Integer,Integer> map=new HashMap<Integer,Integer>();//遍历前两个数组for(int i:nums1){for(int j:nums2){int sum=i+j;map.put(sum,map.getOrDefault(sum,0)+1); }} //统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数for(int i:nums3){for(int j:nums4){res+=map.getOrDefault(0-i-j,0);}}return res;} }
-
收获
- 增强型for循环，for(int i:nums1){}
- map.put(sum, map.getOrDefault(sum, 0) + 1);
- map.getOrDefault(sum, 0) 从map中返回sum键对应的值(出现次数)，当i,j循环的sum出现一次，就+1，只是计算了一个新的值
- map.put() 更新map值
- res是存储符合条件的元组
383赎金信
题目
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
输入：ransomNote = "aa", magazine = "aab" 输出：true
思路
-
我的思路
- 能不能包含，如果在magazine中能查找到ransomNote，就说明包含。
- 怎么样叫做包含？
- 选择结构
- 能不能包含，如果在magazine中能查找到ransomNote，就说明包含。
-
思路
- 原则：不暴露赎金信字迹，字母不可重复使用；假设两个字符串均只含有小写字母。
- record数组存储两个数组的字母出现的字数，一个++，一个–，当最后的record的某个字母<0时，说明false【关键】
-
class Solution {public boolean canConstruct(String ransomNote, String magazine) {int [] record=new int[26];//初始化要正确//第一步判断要加上if (ransomNote.length() > magazine.length()) {return false;}//++for(int i=0;i<magazine.length();i++){record[magazine.charAt(i)-'a']++;}//--for(int j=0;j<ransomNote.length();j++){record[ransomNote.charAt(j)-'a']--;if (record[ransomNote.charAt(j)-'a']<0){return false;}}return true;} }
-
class Solution {public boolean canConstruct(String ransomNote, String magazine) {// shortcutif (ransomNote.length() > magazine.length()) {return false;}// 定义一个哈希映射数组int[] record = new int[26];// 遍历for(char c : magazine.toCharArray()){record[c - 'a'] += 1;}for(char c : ransomNote.toCharArray()){record[c - 'a'] -= 1;}// 如果数组中存在负数，说明ransomNote字符串中存在magazine中没有的字符for(int i : record){if(i < 0){return false;}}return true;} }总结
-
增强型for循环
- for(char c:magazine.toCharArray())[record[c-‘a’]++;
-
字符的用法magazine.charAt(i) 单个字符 magazine.charAt(i)多个字符
-
初步判断要加上，如果ransomNote.length() > magazine.length，就不用进行下去了
15.三数之和
题目
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意： 答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。 * `3 <= nums.length <= 3000` * `-105 <= nums[i] <= 105`
思路
- 我的思路
- 难点在于不能重复，不能暴力循环。
- 选择数据结构，map,key value，遍历一遍，
value为值出现的次数。
- 代码思路
- 选数据结构 数组
- 排序+双指针+去重(这道题挺难的)
- 盲写一遍代码
-
class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> result=new ArrayList<>();//存放结果 Arrays.sort(nums);//排序for(int i=0;i<nums.length;i++){if(nums[i]>0){return result;}//特殊情况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]));//去重b,cwhile (right > left && nums[right] == nums[right - 1]) right--;while (right > left && nums[left] == nums[left + 1]) left++;right--; left++;}}}return result;} }
出现问题
- 动态的二维列表怎么定义的，<>菱形语法，List
<List<Integer>> result=new ArrayList<>() - 注意写前提特殊情况
- 当第一个数>0直接返回结果
- 排序
- Arrays.sort(nums);
- 去重【两个地方的去重】
- 去重a
- 注意是nums[i]==nums[i+1]还是i-1，和left不一样，是i-1
- 需要确保当前值如果和过去的值相等，就不用重复了，如果是i+1,那么还是重复了i+1后计算后，多重复了一次
- 去重b,c
- 之所以用while，是因为要一次性跳过所有重复值为止
- // 去重 b 和 c
while (right > left && nums[right] == nums[right - 1]) right–;
while (right > left && nums[left] == nums[left + 1]) left++; - 之所以是这样，是因为要先保存当前的值，保存完之后，在和下一个值进行比较
- 指针是从前往后的
- 去重a
- while和if的区别
| 特性 | while | if |
|---|
| 功能 | 用于重复执行某些语句，直到条件不满足。 | 用于判断条件是否成立，成立则执行一次语句块。 |
|---|
| 循环性 | 是循环结构，会反复检查条件并执行语句块。 | 是分支结构，条件成立时执行一次语句块，不会重复。 |
|---|
| 条件的检查 | 每次循环前都会检查条件。 | 条件检查一次，只决定是否执行语句块。 |
|---|
18.四数之和
题目
题意：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。【第2个题是等于0，这个是等于target】
注意：
答案中不可以包含重复的四元组。
示例： 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
思路我的思yi题眼：不重复，target
-
- 排序，循环a，去重a
- b到c一个区间，c到d一个区间
- c向左，d从末尾向前到一半。
- target>0时
- cwang
- 再套一层循环，
- 排序，循环a，去重a
- Karl
- 2层for循环，k,i,left,right
- 剪支 注意：不能像三数之和那样判断，nums[i]>target，如果有负数的话，两数相加更小，比如-3，-3，0，0<-5
- 2个剪支
- 3个去重
-
class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> results=new ArrayList<>();Arrays.sort(nums);for(int k=0;k<nums.length;k++){//1剪枝 target包含0if(nums[k]>target&&target>=0){break;} //1去重 if(k>0&&nums[k]==nums[k-1]){continue;}for(int i=k+1;i<nums.length;i++){if(nums[k]+nums[i]>target&&nums[k] + nums[i] >= 0){//二级剪枝，要把两个加一起,必须保证两数之和>0，如果-2-3>-6，不能让停止。break;}if(i>k+1&&nums[i]==nums[i-1]){//二级去重，注意i>k+1开始continue;}int left=i+1;int right=nums.length-1;while(right>left){//终止条件不要忘了加int sum=nums[i]+nums[k]+nums[left]+nums[right];if(sum>target){right--;}if(sum<target){left++;}if (sum==target){results.add(Arrays.asList(nums[k],nums[i],nums[left],nums[right]));//去重,需要加上条件right > left，不然会报错while(right > left&&nums[left]==nums[left+1]){left++;}//加前面的条件是防止跳过的时候交错了一遍去重while(right > left&&nums[right]==nums[right-1]){right--;}left++;right--;}} }}return results;} }
易错点
-
ArrayList和Arrays的使用区别：
- ArrayList，建立列表
- Arrays，使用一些方法，.sort()排序，.asList是将数放在列表中
-
2次剪枝的条件
- 外：>target且target>=0，避开负数的target
- 内：两数之和的剪枝，同时两数之和要>=0，不然会出错，例如：-2-3>-6
-
3次去重
- 第3次去重，是放在sum==target里的，不要放在外面。注意要right>left,如果省略的话，会交错一遍
- while(right > left&&nums[left]==nums[left+1]){left++;}//加前面的条件是防止跳过的时候交错了一遍去重
- while(right > left&&nums[right]==nums[right-1]){right–;}
- left++;right–;
