寸_铁

这个屌丝很懒，什么也没留下！

热门标签

代码随想录算法训练营第七天 | 454.四数相加II | 383. 赎金信 |15. 三数之和 |18.四数之和

作者：寸_铁 | 2024-08-07 15:55:09

踩

代码随想录算法训练营第七天 | 454.四数相加II | 383. 赎金信 |15. 三数之和 |18.四数之和

454.四数相加II

代码

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer, Integer> map = new HashMap<>();
        int temp;
        int res = 0;
        //统计两个数组中的元素之和，同时统计出现的次数，放入map
        for (int i : nums1) {
            for (int j : nums2) {
                temp = i + j;
                if (map.containsKey(temp)) {
                    map.put(temp, map.get(temp) + 1);
                } else {
                    map.put(temp, 1);
                }
            }
        }
        //统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数
        for (int i : nums3) {
            for (int j : nums4) {
                temp = i + j;
                if (map.containsKey(0 - temp)) {
                    res += map.get(0 - temp);
                }
            }
        }
        return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

解题思路

心得

如果map中没有temp这个key,那么就应该把temp的value设置成1

map.put(temp, 1);		//map.put(temp,map.get(temp))
1

如果int res 定义在for循环里面,那么出了for就不能用,所以要定义在外边

如果有好几组四元组都可以相加为0,则+=

res+=map.get((0-temp));   //res=map.get((0-temp));
1

文章

idea 快捷键系列(一)增强for循环_孔汤姆的博客-CSDN博客_idea增强for快捷键

383. 赎金信

代码

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        // 定义一个哈希映射数组
        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;
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

题图

心得

toCharArray就是把字符串转换为字符数组
为什么要对字符串转换成为字符数组?
因为字符串没有索引,不能根据索引找出每个单词
静态初始化和动态初始化的区别：

Java数组必须先初始化，才能使用
字符型变量是什么以及初始化：
这里的return false 是代替了整个大方法末尾的return

res[c-'a']+=1;
					//  res+=res[c-'a']++;
1
2

for (int i:res) 	//只写数组名即可,就可以把数组元素一次传递
					//for (int i = 0; i < res.length; i++)有更简洁的做法
1
2

帖子

[String类中toCharArray()方法的用法_摇摆不定的菜逼的博客-CSDN博客_string.tochararray](https://blog.csdn.net/onlybless/article/details/79537561?ops_request_misc=%7B%22request%5Fid%22%3A%22167090596316800184126846%22%2C%22scm%22%3A%2220140713.130102334…%22%7D&request_id=167090596316800184126846&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2_allsobaiduend~default-1-79537561-null-null.142^v68control,201^v4add_ask,213^v2t3_esquery_v1&utm_term=string toCharArray()&spm=1018.2226.3001.4187)
java中字符串和字符数组_wangyp946的博客-CSDN博客_java字符串和字符数组
Java字符数组与字符串的相互转换_云水冰的博客-CSDN博客
[java字符型变量有几个,Java 字符型变量_我不上层楼了的博客-CSDN博客](https://blog.csdn.net/weixin_42422648/article/details/115778812?ops_request_misc=%7B%22request%5Fid%22%3A%22167090869016800213095136%22%2C%22scm%22%3A%2220140713.130102334.pc%5Fall.%22%7D&request_id=167090869016800213095136&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2_allfirst_rank_ecpm_v1~rank_v31_ecpm-2-115778812-null-null.142^v68control,201^v4add_ask,213^v2t3_esquery_v1&utm_term=java 字符变量&spm=1018.2226.3001.4187)

15. 三数之和

代码

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
	// 找出a + b + c = 0
        // a = nums[i], b = nums[left], c = nums[right]
        for (int i = 0; i < nums.length; i++) {
	    // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
            if (nums[i] > 0) { 
                return result;
            }

            if (i > 0 && nums[i] == nums[i - 1]) {  // 去重a
                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 和 c去重
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;
                    
                    right--; 
                    left++;
                }
            }
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

题图

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bPaT7NWz-1670933499465)(https://gaopunike-test-srt.oss-cn-beijing.aliyuncs.com/img/15.%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C.gif)]

心得:

如果 nums[i] + nums[left] + nums[right] < 0 说明此时三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止
为什么相遇就停止呢
因为如果相遇后右边的穿过左边,左边的穿过右边,那就相当于还是和刚才来的路径一样,只不过是左右指针调换了名称而已
三元组的去重:a不能是两次a,但是a和b不能是相等的
a的去重:nums[i] == nums[i - 1]

  if (i > 0 && nums[i] == nums[i - 1]) {  // 去重a,而不是nums[i] == nums[i +1],因为这样的话,nums[i]也不会执行
1

continue是跳出此次循环继续执行
比如打印1-5,在4情况下continue,就打印1,2,3,5;
Arrays.sort(int[] a) 这种形式是对一个数组的所有元素进行排序，并且是按从小到大的顺序。

String str = Arrays.toString(arr); // Arrays类的toString()方法能将数组中的内容全部打印出来
						//输出：[3, 2, 1, 5, 4]
1
2

Arrays.asList():

向result里面添加的必须是集合 result.add(集合)

 List<List<Integer>> result = new ArrayList<>();
1

       // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
           if (nums[i] > 0) { 
               return result
                   //因为后面的数字都是比这个数字大的,所以不可能相加和为0
1
2
3
4

        while (right > left)
       					//我们要求的是三数之和,如果left=right那么就是两数之和,不符合条件  
    ```
    
1
2
3
4

ahk只能搜狗输入法使用

         // 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
                           while (right > left && nums[right] == nums[right - 1]) right--;
                           while (right > left && nums[left] == nums[left + 1]) left++;
     ```
     
1
2
3
4
5

(b和c去重)
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zjRNsOhq-1670933499466)(C:\Users\86130\AppData\Roaming\Typora\typora-user-images\image-20221213164647439.png)]
我们要到是java.util的Arrays
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CojMbIYo-1670933499466)(C:\Users\86130\AppData\Roaming\Typora\typora-user-images\image-20221213170316199.png)]
我们要的是外部的索引,不是内部的元素

 int right = nums.length - 1;
//int right=nums[nums.length-1]
1
2

以后还是要在else后面添加括号,后面的一大堆代码都是这种情况里面的,而你却认为只有一句
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AtZbK1Uz-1670933499466)(C:\Users\86130\AppData\Roaming\Typora\typora-user-images\image-20221213172343849.png)]

 else {
1

文章

18.四数之和

代码

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
       
        for (int i = 0; i < nums.length; i++) {
		
            // nums[i] > target 直接返回, 剪枝操作
            if (nums[i] > 0 && nums[i] > target) {
                return result;
            }
		
            if (i > 0 && nums[i - 1] == nums[i]) {    // 对nums[i]去重
                continue;
            }
            
            for (int j = i + 1; j < nums.length; j++) {

                if (j > i + 1 && nums[j - 1] == nums[j]) {  // 对nums[j]去重
                    continue;
                }

                int left = j + 1;
                int right = nums.length - 1;
                while (right > left) {
		    // nums[k] + nums[i] + nums[left] + nums[right] > target int会溢出
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                     if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        // 对nums[left]和nums[right]去重
                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;

                        left++;
                        right--;
                    }
                }
            }
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

心得

 // nums[k] + nums[i] + nums[left] + nums[right] > target int会溢出
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
1
2

为什么呢?

为什么?
    if (nums[i] > 0 && nums[i] > target)
1
2

最外层的for既去重又剪枝,第二层只去重就行,里面的双指针获取了之后在去重

//i>0是因为,第一位是a,如果i=0,nums[0]==nums[-1],
if (i>0&&nums[i]==nums[i-1])
1
2

数组索引从0开始,没有[-1]
left和right指针的移动靠外边循环和自身+±-
关于去重:
一定是先取上最外边的值,然后去掉内部的重复的
对于right:一定是先取到了外边的nums[right],然后对内部的nums[right-1]去重
```
nums[right]==nums[right-1]
1
```
同理,left的判定条件一定是与==nums[left+1]==相等

但是前提条件是不能够越位,即while(right>left)而不是i>0
//while (i>0&&nums[right]==nums[right-1])right--;
1
2

微软的键盘能够取消撤销即:ctrl+shift+z(所以还不能取缔掉而只用搜狗)

忘记Arrays.sort(nums);
1

j>i+1
//if(j>0&&nums[j]==nums[j-1])
1
2

外面的大条件没有写,内部的left和right走不起来
// while (right > left) {
1
2

文章

[Java数组简介：数组是什么？ (biancheng.net)](http://c.biancheng.net/view/906.html#:~:text=数值数组元素的默认值为 0，而引用元素的默认值为 null。数组的索引从 0,开始，如果数组有 n 个元素，那么数组的索引是从 0 到（n-1）。)
史上最全的IDEA快捷键总结_扬帆向海的博客-CSDN博客_idea快捷键

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】