当前位置：首页 > news >正文

Leetcode 01 java

news 来源：原创 2025/7/13 3:59:41

两数之和

/*
给定一个整数数组 nums 和一个整数目标值 target，
请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。*/

1 处理字符串格式输入

Q: 只给提示不给答案，我的意思是，题目给我的输入就是nums = [2,7,11,15], target = 9，这和平时我们就淳朴的输入2 7 11 15 9 不太一样，我要怎么处理，给点提示？

你需要处理的是类似 nums = [2,7,11,15], target = 9 这样的字符串格式输入，而不是直接的整数数组。以下是关键提示：

提示 1：字符串解析

提取数组部分：从输入中分离出 [2,7,11,15] 和 9。
去除括号：将 [2,7,11,15] 转换为 2,7,11,15。
分割字符串：用逗号分隔每个元素，得到字符串数组 ["2", "7", "11", "15"]。

提示 2：字符串转整数

将字符串数组（如 ["2", "7"]）转换为整数数组（如 [2, 7]）。
使用 Integer.parseInt() 方法。

提示 3：提取目标值

从 target = 9 中提取出整数 9。
可以先按 = 分割字符串，再转换为整数。

提示 4：示例步骤

输入字符串：nums = [2,7,11,15], target = 9
分割为两部分：
- nums = [2,7,11,15]
- target = 9
处理数组部分：
- 去除 nums = [ 和 ]，得到 2,7,11,15。
- 按逗号分割，转换为整数数组。
处理目标值：
- 提取 9 并转换为整数。

工具提示

使用 String.split() 方法分割字符串。
使用 String.trim() 方法去除空格。
使用 substring() 方法截取子字符串。

建议：先尝试手动解析示例输入，再编写代码实现。如果遇到具体问题（如括号处理），可以进一步提问。

2 我只需要实现方法签名不需要实现main函数，其实给自己徒增烦恼了虚晃一枪~

这个函数签名 public int[] twoSum(int[] nums, int target) 是题目要求你实现的核心算法部分，它接收一个整数数组 nums 和一个目标值 target，需要返回两个下标组成的数组。

关键理解：

函数作用：
你不需要处理输入输出（如读取 nums = [2,7,11,15], target = 9 这样的字符串），只需要实现算法逻辑。
- 调用示例：
  twoSum(new int[]{2, 7, 11, 15}, 9) → 应返回 [0, 1]。
输入参数：
- nums：已经是整数数组（无需自己解析字符串）。
- target：已经是整数（无需自己提取和转换）。
返回值：
- 返回一个包含两个下标的整数数组，表示和为 target 的两个数的位置。

示例调用流程（你不需要写这段代码，仅用于理解）：

java

// 主函数（你不需要实现这个，仅为示例）
public static void main(String[] args) {int[] nums = {2, 7, 11, 15};int target = 9;int[] result = twoSum(nums, target); // 调用你实现的方法System.out.println(Arrays.toString(result)); // 输出 [0, 1]
}

你需要做的：

在 twoSum 方法内部实现算法逻辑，找到两个数的下标并返回。例如：

java

public int[] twoSum(int[] nums, int target) {// 遍历数组，找到两个数的和等于target// 返回它们的下标，例如 new int[]{0, 1}
}

提示：

可以使用暴力法（双重循环）或哈希表优化。
不需要处理输入输出，只需要关注算法本身。
确保返回的下标是有效的（例如，不要返回负数或越界的下标）

3 return 字符串怎么写？

对于这道题目！其实不可以写成字符串，原来的方法签名里面声明的是int类型，我可以返回数组哦！！

我原来的错误的代码

class Solution {public int[] twoSum(int[] nums, int target) {int n = nums.length;int[] a = null;for (int i = 0; i < n; i++) {for (int j = n - 1; j > i; j--) {if (nums[i] + nums[j] == target) {a[0]=i;a[1]=j;}}}return a;}
}

报错：

java.lang.NullPointerException: Cannot store to int array because "<local4>" is null at line 8, Solution.twoSum at line 56, __DriverSolution__.__helper__ at line 89, __Driver__.main

因为数组a被初始化为null，却直接被用来存储索引值。

修改后：

class Solution {public int[] twoSum(int[] nums, int target) {int n = nums.length;for (int i = 0; i < n; i++) {for (int j = n - 1; j > i; j--) {if (nums[i] + nums[j] == target) {return new int[]{i, j};}}}return new int [0];}
}

当前的双重循环方法效率较低（时间复杂度为 O (n²)）

4 哈希表优化，改进建议：

如果你需要处理大规模数据，当前的双重循环方法效率较低（时间复杂度为 O (n²)）。可以使用哈希表将时间复杂度优化到 O (n)：

java

import java.util.HashMap;
import java.util.Map;class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {int complement = target - nums[i];if (map.containsKey(complement)) {return new int[]{map.get(complement), i};}map.put(nums[i], i);}return new int[0];}
}

这个优化版本使用哈希表记录每个元素的索引，只需遍历数组一次。

5 `NullPointerException`（空指针异常）

在 Java 编程里，NullPointerException（空指针异常）是一种极为常见的运行时异常。当程序试图对一个值为null的对象引用进行操作时，就会触发该异常。下面为你详细介绍它的相关情况：

1. 触发原因

当出现以下这些操作时，就可能引发NullPointerException：

调用null对象的方法。
访问或修改null对象的字段。
获取null对象的长度，就像把null当作数组去操作。
访问或修改null对象的数组元素。
把null当作Throwable类型来抛出。

2. 典型示例

下面通过一些代码示例，展示NullPointerException是如何产生的：

java

// 示例1：调用null对象的方法
String str = null;
str.length(); // 这里会抛出NullPointerException// 示例2：访问null对象的字段
class Person {String name;
}
Person p = null;
p.name = "John"; // 这行代码会触发异常// 示例3：操作null数组
int[] arr = null;
arr[0] = 1; // 此处会引发异常

3. 解决办法

为了避免出现NullPointerException，可以采用以下几种方法：

进行空值检查
在使用对象之前，先判断它是否为null：

java

if (str != null) {System.out.println(str.length());
}

合理初始化对象
在声明对象时，就对其进行初始化：

java

String str = ""; // 初始化为空字符串，而非null

使用Optional类
Java 8 引入的Optional类，能有效避免显式的空值检查：

java

import java.util.Optional;Optional<String> optStr = Optional.ofNullable(str);
optStr.ifPresent(s -> System.out.println(s.length()));

借助 IDE 工具
利用 IDE 的静态分析功能，比如 IntelliJ IDEA 的@NotNull注解：

java

public void printLength(@NotNull String str) {System.out.println(str.length());
}

4. 调试建议

当遇到NullPointerException时，可以按照以下步骤进行调试：

查看异常堆栈信息，确定是哪一行代码抛出了异常。
找出导致null的对象引用。
分析这个引用为什么会是null，是赋值失败，还是没有正确初始化。
添加必要的空值检查或者初始化代码。

5. 在你的代码中出现的问题

在你之前提供的代码里：

java

int[] a = null;
// ...
a[0] = i; // 这里会抛出NullPointerException，因为a为null

要解决这个问题，应该在使用数组之前对其进行初始化：

java

int[] a = new int[2]; // 初始化数组
a[0] = i;
a[1] = j;

不过更好的做法是直接返回一个新数组：

java

return new int[]{i, j};

总结

NullPointerException是由于对null对象进行操作而引发的。要避免这种异常，关键在于进行严格的空值检查、合理初始化对象，或者使用像Optional这样的工具类。在调试时，要仔细分析异常堆栈信息，找出导致null的根源。

6 java中的哈希表（Hash Table）

在 Java 中，哈希表是通过一系列实现了Map接口的类来实现的，主要包括HashMap、Hashtable、LinkedHashMap和TreeMap等。这些类各有特点，但核心原理都是基于哈希函数实现键值对的快速存储和检索。

核心类与特点

1. HashMap

特点：
- 线程不安全，允许null键和null值。
- 无序，不保证元素顺序。
- 初始容量为 16，负载因子 0.75（当元素数量超过容量 × 负载因子时自动扩容）。
基本用法：

java

import java.util.HashMap;
import java.util.Map;public class HashMapExample {public static void main(String[] args) {// 创建HashMapMap<String, Integer> map = new HashMap<>();// 添加元素map.put("apple", 1);map.put("banana", 2);map.put(null, 0); // 允许null键// 访问元素System.out.println(map.get("apple")); // 输出: 1// 遍历元素for (Map.Entry<String, Integer> entry : map.entrySet()) {System.out.println(entry.getKey() + ": " + entry.getValue());}// 删除元素map.remove("banana");}
}

2. Hashtable

特点：
- 线程安全（所有方法都被synchronized修饰），但性能较低。
- 不允许null键或null值，否则抛出NullPointerException。
- 继承自Dictionary类，已逐渐被HashMap替代。
基本用法：

java

import java.util.Hashtable;
import java.util.Map;public class HashtableExample {public static void main(String[] args) {Map<String, Integer> table = new Hashtable<>();table.put("apple", 1);table.put("banana", 2);// table.put(null, 0); // 报错: NullPointerException}
}

3. LinkedHashMap

特点：
- 继承自HashMap，维护插入顺序或访问顺序（通过构造函数参数指定）。
- 适合需要按顺序遍历的场景，如实现 LRU 缓存。
示例（按访问顺序排序）：

java

import java.util.LinkedHashMap;
import java.util.Map;public class LinkedHashMapExample {public static void main(String[] args) {// 第三个参数true表示按访问顺序排序LinkedHashMap<String, Integer> linkedMap = new LinkedHashMap<>(16, 0.75f, true) {@Overrideprotected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {return size() > 3; // 保持最多3个元素，超出时移除最老的}};linkedMap.put("a", 1);linkedMap.put("b", 2);linkedMap.put("c", 3);linkedMap.get("a"); // 访问"a"，使其变为最近访问linkedMap.put("d", 4); // 插入"d"，触发移除最老的"b"System.out.println(linkedMap); // 输出: {c=3, a=1, d=4}}
}

4. TreeMap

特点：
- 基于红黑树实现，按键的自然顺序或自定义比较器排序。
- 不允许null键（除非自定义比较器支持）。
- 适合需要有序遍历的场景（如范围查询）。
示例（按键排序）：

java

import java.util.Map;
import java.util.TreeMap;public class TreeMapExample {public static void main(String[] args) {Map<Integer, String> treeMap = new TreeMap<>();treeMap.put(3, "apple");treeMap.put(1, "banana");treeMap.put(2, "cherry");// 按键升序输出for (Map.Entry<Integer, String> entry : treeMap.entrySet()) {System.out.println(entry.getKey() + ": " + entry.getValue());}// 输出: // 1: banana// 2: cherry// 3: apple}
}

哈希冲突处理

当两个不同的键产生相同的哈希值时，Java 的哈希表使用 ** 链地址法（Chaining）** 处理冲突：

每个哈希桶（Bucket）存储一个链表或红黑树。
当冲突元素较少时，使用链表；当链表长度超过 8 且容量≥64 时，自动转换为红黑树（JDK 8+），以提高查询效率。

性能优化

初始容量与负载因子：
- 预估元素数量，避免频繁扩容。
- 负载因子越小，空间换时间，冲突概率降低；反之则节省空间但可能增加冲突。
键的设计：
- 键必须正确重写hashCode()和equals()方法。
- 示例：

java

public class Person {private String name;private int age;// 构造函数、getter/setter省略@Overridepublic int hashCode() {return Objects.hash(name, age); // JDK 7+ 推荐写法}@Overridepublic boolean equals(Object obj) {if (this == obj) return true;if (obj == null || getClass() != obj.getClass()) return false;Person other = (Person) obj;return age == other.age && Objects.equals(name, other.name);}
}

线程安全方案

Hashtable：所有方法同步，性能差。
Collections.synchronizedMap()：包装HashMap，实现同步。
ConcurrentHashMap（推荐）：
- 分段锁（JDK 7 及以前）或 CAS（JDK 8+）实现高效并发。
- 允许并发读写，读操作无锁，写操作仅锁定当前桶。

java

import java.util.concurrent.ConcurrentHashMap;public class ConcurrentHashMapExample {public static void main(String[] args) {ConcurrentHashMap<String, Integer> concurrentMap = new ConcurrentHashMap<>();concurrentMap.put("apple", 1);concurrentMap.putIfAbsent("banana", 2); // 原子操作，避免竞态条件}
}

应用场景

缓存（如 LRU 缓存）。
数据库索引。
统计频率（如词频统计）。
唯一性检查（如判断元素是否存在）。

通过合理选择哈希表实现类和参数调优，可以在各种场景中发挥其 O (1) 时间复杂度的优势。

1 处理字符串格式输入

提示 1：字符串解析

提示 2：字符串转整数

提示 3：提取目标值

提示 4：示例步骤

工具提示

2 我只需要实现方法签名不需要实现main函数，其实给自己徒增烦恼了虚晃一枪~

关键理解：

示例调用流程（你不需要写这段代码，仅用于理解）：

你需要做的：

提示：

3 return 字符串怎么写？

4 哈希表优化，改进建议：

5 NullPointerException（空指针异常）

1. 触发原因

2. 典型示例

3. 解决办法

4. 调试建议

5. 在你的代码中出现的问题

总结

6 java中的哈希表（Hash Table）

核心类与特点

1. HashMap

2. Hashtable

3. LinkedHashMap

4. TreeMap

哈希冲突处理

性能优化

线程安全方案

应用场景

相关文章：

5 `NullPointerException`（空指针异常）