Amber-Leedcode-Java-代码随想录打卡第七天 ｜ 454.四数相加II 383. 赎金信 15. 三数之和 18. 四数之和

前言

继续加油，嘻嘻

454.四数相加

1.初见

没想法。。

2.看完解题思路后

只需要返回个数，不用返回具体的位置, 有了这个思路后就好办了。而且使得AB相加，CD相加，最后找值，看其是否出现在C的hashmap中就好了，如果在的话，就相乘他们的value。一次就过啦！

3.代码部分

获取键，在遍历中十分有用?

Integer v:resultAB.keySet()

?修改value的值 (其实还是不太明白什么时候应该写int，什么时候应该写integer，后来试了一下发现用int也是可以赋值的)

  Integer value = resultAB.get(nums1[i] + nums2[j]);
                    value = value + 1;
                    resultAB.put(nums1[i] + nums2[j], value);

更新：chat老师的解答

1. 什么时候应该写int，什么时候应该写integer

在Java中，`int` 和 `Integer` 的选择取决于具体的使用场景和需求。下面是关于何时使用 `int` 和何时使用 `Integer` 的一些指导：

1. **使用 `int`：**
? ?- **基本类型：** `int` 是Java的一种基本数据类型，用于表示整数值。它不是一个对象，因此在内存中占用较少的空间，并且在处理时比 `Integer` 快。
? ?- **性能关键场景：** 如果你的代码在性能上非常敏感，比如在大量数值运算或高频率循环中，使用 `int` 可以减少自动装箱和拆箱的开销，提高效率。
? ?- **默认值为0：** 在Java中，未初始化的 `int` 变量会默认为0，而 `Integer` 的默认值是 `null`。

2. **使用 `Integer`：**
? ?- **对象类型：** `Integer` 是Java的一个包装类，它将基本数据类型 `int` 封装成一个对象。这使得你可以在需要对象而不是基本类型的地方使用 `Integer`。
? ?- **泛型中的使用：** Java的泛型不支持基本数据类型，所以在使用泛型集合（如 `ArrayList`、`HashMap`）时，你需要使用 `Integer`。
? ?- **可以为 `null`：** `Integer` 可以为 `null`，这在某些情况下可以表示某个值是“未设置”或“不存在”的状态。
? ?- **自动装箱和拆箱：** 自Java 5起，Java支持自动装箱（将 `int` 转换为 `Integer`）和自动拆箱（将 `Integer` 转换回 `int`）。这简化了 `int` 和 `Integer` 之间的转换。

**应用示例：**
- 在定义集合元素、使用泛型、或者需要处理 `null` 值时，你应该使用 `Integer`。
- 在进行大量数学运算或者需要高性能处理时，尤其是对内存使用和执行速度有严格要求的场景，应该使用 `int`。

总的来说，选择 `int` 或 `Integer` 主要取决于你的应用场景是更注重性能还是更需要对象的特性和灵活性。

2.自动装箱和拆箱

自动装箱和自动拆箱是Java 5及以后版本中引入的两个特性，用于简化基本类型和它们对应的包装类之间的转换。这里的基本类型指的是如 `int`，`double`，`char` 等，而包装类则是如 `Integer`，`Double`，`Character` 等。

1. **自动装箱（Autoboxing）：**
? ?- 自动装箱是指Java自动将基本类型转换为对应的包装类对象的过程。例如，当你将一个 `int` 赋值给 `Integer` 类型的变量时，Java会自动将这个 `int` 转换为 `Integer`。
? ?- 例如：`Integer num = 10;` 在这里，基本类型 `int` 的值10被自动装箱成 `Integer` 类型。

2. **自动拆箱（Unboxing）：**
? ?- 自动拆箱是指Java自动将包装类对象转换为对应的基本类型值的过程。例如，当你将一个 `Integer` 类型的对象赋值给 `int` 类型的变量时，Java会自动将这个 `Integer` 对象转换为 `int`。
? ?- 例如：`int num = new Integer(10);` 在这里，`Integer` 对象被自动拆箱成 `int` 类型。

这两个特性的引入极大地简化了编程过程，因为它允许程序员在基本类型和包装类之间进行无缝转换，而无需手动进行类型转换。这在处理集合、泛型等需要对象而不是基本类型的场景中特别有用。

然而，需要注意的是，自动装箱和拆箱虽然方便，但也可能引起性能问题（特别是在大量操作中）和空指针异常（当尝试对 `null` 的包装类进行拆箱时）。因此，理解这两个概念在实际应用中的影响是很重要的。

3.

4.Code?

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {

        int count = 0;

        HashMap<Integer,Integer> resultAB = new HashMap<Integer,Integer>();


        HashMap<Integer,Integer> resultCD = new HashMap<Integer,Integer>();

        for (int i = 0;i<nums1.length;i++){
            for (int j = 0;j<nums1.length;j++){
                if (resultAB.containsKey(nums1[i] + nums2[j])){
                    Integer value = resultAB.get(nums1[i] + nums2[j]);
                    value = value + 1;

                resultAB.put(nums1[i] + nums2[j], value);
                }else{
                    resultAB.put(nums1[i] + nums2[j],1);
                }


                if (resultCD.containsKey(nums3[i] + nums4[j])){
                    Integer value = resultCD.get(nums3[i] + nums4[j]);
                    value = value + 1;

                resultCD.put(nums3[i] + nums4[j], value);
                }else{
                    resultCD.put(nums3[i] + nums4[j],1);
                }
            }
        }

        for (Integer v:resultAB.keySet()){
            Integer res = 0 - v;
            if (resultCD.containsKey(res)){
                int number = resultCD.get(res) * resultAB.get(v);
                count = count + number;
            }
        }
        return count;
    }
}

?383. 赎金信

比较简单

但需要注意的是：

1.问题

（1）HashMap初始化

需要Character而不是char

HashMap<Character,Integer> mag = new  HashMap<Character,Integer>();

在Java中，当你使用 HashMap 或其他泛型集合时，需要使用对象类型而不是基本类型，这是因为Java泛型不支持基本类型，如 char、int 等。泛型仅支持对象类型，比如 Character、Integer 等包装类。（c老师）?

?（2）空间复杂度的问题

（使用数组来映射而不是hashmap），来自代码随想录

哈希解法

因为题目说只有小写字母，那可以采用空间换取时间的哈希策略，用一个长度为26的数组来记录magazine里字母出现的次数。

然后再用ransomNote去验证这个数组是否包含了ransomNote所需要的所有字母。

依然是数组在哈希法中的应用。

一些同学可能想，用数组干啥，都用map完事了，其实在本题的情况下，使用map的空间消耗要比数组大一些的，因为map要维护红黑树或者哈希表，而且还要做哈希函数，是费时的！数据量大的话就能体现出来差别了。 所以数组更加简单直接有效！

2.Code

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {

        HashMap<Character,Integer> mag = new  HashMap<Character,Integer>();

        for (int i = 0;i < magazine.length();i++){
            if (mag.containsKey(magazine.charAt(i))){
                int value = mag.get(magazine.charAt(i));
                value = value + 1;
                mag.put(magazine.charAt(i),value);
            }else{
                mag.put(magazine.charAt(i),1);
            }
        }

        for (int i = 0;i < ransomNote.length();i++){
            if (mag.containsKey(ransomNote.charAt(i))){
                int value = mag.get(ransomNote.charAt(i));
                value = value - 1;
                if (value == 0){
                    mag.remove(ransomNote.charAt(i));
                }else{
                    mag.put(ransomNote.charAt(i),value);
                }
            }else{
                return false;
            }
        }

        return true;

    }
}

3.他人Code - 使用数组?

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        // shortcut
        if (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;
    }
}

15. 三数之和

1.问题

（1）去重的操作

在这里为了判断是否left与right已经移动了，使用变量来记录是否移动。

   boolean flag_left = false;
   boolean flag_right = false;

?（2）list和arraylist的关系

数组的初始化，要分清list和arraylist的关系。待解决，感觉要深刻理解，collection，list，arraylist之间的关系，现在只是会使用。

更新 ：chat老师的解答我感觉很清晰，可能可以告诉我们原因

1.???????list和arraylist之间的关系

在Java中，`List` 和 `ArrayList` 之间的关系可以通过接口和实现类来理解。`List` 是一个接口，它定义了一系列操作列表数据的方法，比如添加、删除、获取元素等。`ArrayList` 是 `List` 接口的一个具体实现，它通过数组的方式来存储数据。

举个例子，当你写 `List<List<Integer>> result = new ArrayList<List<Integer>>();` 时，你实际上在做两件事：

1. **声明一个接口类型的变量：** `List<List<Integer>> result` 声明了一个可以存储 `List<Integer>` 类型对象的列表。这里的 `List` 是一个接口，你不能直接实例化一个接口，因为它只定义了行为，而没有具体实现。

2. **实例化一个实现类对象：** `new ArrayList<List<Integer>>()` 创建了一个 `ArrayList` 的实例。`ArrayList` 是 `List` 接口的一个具体实现，提供了接口中定义的所有方法的实现。这里你用 `ArrayList` 来实例化 `List`，这是因为Java支持多态，即你可以用实现类的对象来实例化接口类型的变量。

通过这种方式，Java程序员可以编写更加通用和灵活的代码。你可以在不改变代码结构的情况下，替换不同的实现。例如，如果你想要一个线程安全的列表，你可以简单地将 `ArrayList` 替换为 `Vector` 或 `CopyOnWriteArrayList`，而不需要改变使用这个列表的代码。

这种设计也使得Java的集合框架非常强大。你可以定义一个接口类型的集合，然后根据需要选择最合适的实现。例如，如果你需要频繁地在列表中间插入或删除元素，`LinkedList` 可能是一个比 `ArrayList` 更好的选择。但是在这两种情况下，使用这个列表的代码可以保持不变。

总之，通过使用接口和具体实现类，Java提供了一种非常灵活和强大的方式来处理各种不同的数据结构，同时也使得代码更加模块化和可重用。

2.new ArrayList<List<Integer>>()为什么这里面List<Integer>的list没有改变呢？

在表达式 `new ArrayList<List<Integer>>()` 中，`List<Integer>` 没有改变的原因是因为这里的 `List<Integer>` 指定了 `ArrayList` 中将要存储的元素类型。具体来说：

1. **泛型（Generics）的使用：** `List<Integer>` 是一个泛型表达式，它指定了列表中应该存储的元素类型。在这个例子中，每个元素都是 `Integer` 类型的列表，即 `List<Integer>`。

2. **声明集合类型：** 当你使用 `new ArrayList<List<Integer>>()` 创建一个新的 `ArrayList` 实例时，你正在告诉Java，这个 `ArrayList` 将会存储 `List<Integer>` 类型的对象。这就是为什么 `List<Integer>` 在这里没有改变的原因：它是定义 `ArrayList` 将要存储的数据类型。

3. **类型安全和灵活性：** 泛型使得集合更加类型安全，同时也增加了灵活性。在这种情况下，你可以确信这个 `ArrayList` 只会存储 `List<Integer>` 类型的对象，这减少了运行时的类型错误。同时，你也可以轻松地改变存储在 `ArrayList` 中的对象类型，只需改变泛型参数即可。

4. **多态性：** 尽管 `ArrayList` 被声明为存储 `List<Integer>` 类型的对象，但你仍然可以存储任何 `List` 接口的实现，比如 `ArrayList<Integer>`, `LinkedList<Integer>` 等。这是因为它们都是 `List` 接口的实现。

总结来说，`new ArrayList<List<Integer>>()` 中的 `List<Integer>` 指定了这个 `ArrayList` 的元素类型，而这个类型在声明时就已经被确定了，所以在实例化 `ArrayList` 的时候不会改变。这是Java泛型提供的功能，旨在提高代码的灵活性和类型安全性。

3.那可以写为 ArrayList<ArrayList<Integer>>()吗

是的，你完全可以将 `new ArrayList<List<Integer>>()` 写作 `new ArrayList<ArrayList<Integer>>()`，但这两种写法在使用上有所不同。

1. **`new ArrayList<List<Integer>>()`：** 这种写法表示你创建了一个 `ArrayList`，其元素是 `List<Integer>` 类型的对象。这意味着这个 `ArrayList` 可以存储任何实现了 `List` 接口的对象，如 `ArrayList<Integer>`, `LinkedList<Integer>`, `Vector<Integer>` 等。这种写法提供了更多的灵活性。

2. **`new ArrayList<ArrayList<Integer>>()`：** 这种写法表示你创建的 `ArrayList` 只能存储 `ArrayList<Integer>` 类型的对象。这意味着你不能将 `LinkedList<Integer>` 或其他 `List` 接口的实现类的实例添加到这个 `ArrayList` 中。这种写法限制了你可以存储的对象类型。

选择哪种写法取决于你的具体需求：

- 如果你需要在你的 `ArrayList` 中存储不同类型的 `List` 实现，那么 `new ArrayList<List<Integer>>()` 是更好的选择。
- 如果你确定只会使用 `ArrayList<Integer>` 类型的对象，并且希望限制列表中元素的类型，那么 `new ArrayList<ArrayList<Integer>>()` 会是一个更合适的选择。

if (nums.length < 3){
          return new ArrayList<>(); 
      }else if (nums.length == 3){
          if (nums[0] + nums[1] + nums[2] == 0){
            return Arrays.asList(Arrays.asList(nums[0], nums[1], nums[2]));
          }else{
              return new ArrayList<>(); 
          }
      }

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

（3）排序

 Arrays.sort(nums);

2.精华笔记

?

3.code?

class Solution {
   
  public List<List<Integer>> threeSum(int[] nums) {
      if (nums.length < 3){
          return new ArrayList<>(); 
      }else if (nums.length == 3){
          if (nums[0] + nums[1] + nums[2] == 0){
            return Arrays.asList(Arrays.asList(nums[0], nums[1], nums[2]));
          }else{
              return new ArrayList<>(); 
          }
      }
     Arrays.sort(nums);
     boolean flag_left = false;
     boolean flag_right = false;
     List<List<Integer>> result = new ArrayList<List<Integer>>();
     for (int i = 0;i < nums.length -2;i++){
         int left = i + 1;
         int right = nums.length - 1;
         while (right > left){
             if (i > 0 && nums[i] == nums[i-1]){
             break;
         }
         if (nums[i] + nums[left] + nums[right] == 0){
             if (left != i+1 && right != nums.length - 1){
                 if (nums[left] == nums[left - 1]){
                     left ++;
                     flag_left = true;
                 }else{
                     flag_left = false;
                 }
                 if (nums[right] == nums[right + 1]){
                     right--;
                     flag_right = true;
                 }else{
                     flag_right = false;
                 }
                 if (nums[i] + nums[left] + nums[right] == 0 && flag_left == false && flag_right == false){
                     if (right > left){
                         result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                   left ++;
                   right--;
                     }
                 }
             }else{
                   result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                   left ++;
                   right--;
             }
         }else if (nums[i] + nums[left] + nums[right] < 0){
             left ++;
         }else if (nums[i] + nums[left] + nums[right] > 0){
             right --;
         }
         }
     }
     return result;
           
}
}

18. 四数之和

自己写的，其实就是多加一个循环

1.值得注意的点

（1）超出长度溢出

为什么这个程序在面对[1000000000,1000000000,1000000000,1000000000]这个测试用例的时候会出错？

回答

您的程序在面对 [1000000000, 1000000000, 1000000000, 1000000000] 这样的测试用例时出错的原因是整数溢出。在您的代码中，您对数组中的数进行了加法操作，例如 nums[i] + nums[j] + nums[left] + nums[right]。当这些数值非常大时，加起来的总和可能会超过 int 类型的最大值（即 Integer.MAX_VALUE，大约是 2^31-1），导致整数溢出。

在Java中，当整数溢出时，它不会抛出异常，而是会绕回到最小值并继续计数。这意味着加法结果可能是一个完全不同的、错误的数值。

要解决这个问题，您可以在进行加法操作之前进行范围检查，或者将相关变量的类型更改为 long，以便处理更大的数值。不过，在这种情况下，由于所有的数字都是 1000000000，即使将它们转换为 long 类型也无法避免加和超出 int 范围。因此，更好的做法是在加法操作之前进行检查。

代码

long sum = (long) nums[i] + (long) nums[j] + (long) nums[left] + (long) nums[right];

（2）使用了一种新的剪枝操作，之前是设置boolean，现在改为在相等后，进行这样的操作，就不用boolean了，很快捷高效啊

else if (sum == target){
                     result.add(Arrays.asList(nums[i], nums[j], nums[left],nums[right]));
                     while (right > left && nums[left] == nums[left + 1]){
                         left ++;
                     }
                     while (right > left && nums[right] == nums[right - 1]){
                         right --;
                     }
                     left ++;
                     right --;

?（3）多的一次循环为

   for (int j = i + 1; j < length - 2;j++){
            if (j > i + 1 && nums[j] == nums [j-1]){
                continue;
            }

2.Code?

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {

    int length = nums.length;
    if (length < 4){
        return new ArrayList<>();
    }else if (length == 4){
        long sum = (long) nums[0] + (long) nums[1] + (long) nums[2] + (long) nums[3];
        if ( sum == target){
            return Arrays.asList(Arrays.asList(nums[0],nums[1],nums[2],nums[3]));
        }else{
            return new ArrayList<>();
        }
    }
    Arrays.sort(nums);
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    for (int i = 0;i < length - 3;i++){
        if (i > 0 && nums[i] == nums[i-1]){
            continue;
        }
        for (int j = i + 1; j < length - 2;j++){
            if (j > i + 1 && nums[j] == nums [j-1]){
                continue;
            }
            int left = j + 1;
            int right = length - 1;
            while (right > left){
                long sum = (long) nums[i] + (long) nums[j] + (long) nums[left] + (long) nums[right];
                 if (sum < target){
                     left ++;
                 }else if (sum > target){
                     right --;
                 }else if (sum == target){
                     result.add(Arrays.asList(nums[i], nums[j], nums[left],nums[right]));
                     while (right > left && nums[left] == nums[left + 1]){
                         left ++;
                     }
                     while (right > left && nums[right] == nums[right - 1]){
                         right --;
                     }
                     left ++;
                     right --;
                 }
            }
        }
    }
    return result;





    }
}

总结：

1. 状态：进度百分之90，还是有一些点需要注意，还有一些点没有解决，主要是代码书写的问题，不是逻辑的问题 -------->?更新：暂时完结
2. 学习2小时左右
3. 困难：逻辑的考虑
4. 待解决问题：
5. 今日收获：很多。
6. 来源：代码随想录