LeetCode 1.

问题描述

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

原因分析：

想法一：使用俩次循环遍历。但是时间复杂度太高O(n^2)

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

class Solution { public int[] twoSum(int[] nums, int target) { // 外层循环遍历每个元素（除了最后一个） for (int i = 0; i < nums.length - 1; i++) { // 内层循环遍历当前元素之后的所有元素 for (int j = i + 1; j < nums.length; j++) { // 检查两数之和是否等于目标值 if (nums[i] + nums[j] == target) {  // 找到解，立即返回索引对  return new int[]{i, j}; } } } // 理论上不会执行到这里（题目保证有解） return new int[0]; // 保证编译通过 }}

解决方案：

遇到判断这个元素是否在集合里出现过的时候（哈希表法）：里面有俩种结构（数组与Set）做哈希映射

import java.util.HashMap;class Solution { public int[] twoSum(int[] nums, int target) { // 创建哈希表：键=数组元素值(Integer), 值=元素索引(Integer) HashMap<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]; // 创建新的空数组对象 }}

二、Set 与 Map 的关系与区别

1. Map（映射）：键值对集合

核心特征：

• 存储键值对（Key-Value pairs）
• 键唯一，值可重复
• 通过键快速检索值

// Java HashMap 示例Map<String, Integer> map = new HashMap<>();map.put(\"apple\", 1); // 插入键值对int count = map.get(\"apple\"); // 通过键获取值

2. Set（集合）：唯一元素容器

核心特征：

• 存储不重复的元素
• 本质是键的集合（值被忽略）
• 基于 Map 实现（值用固定占位对象）

// Java HashSet 源码（简化版）public class HashSet<E> { private transient HashMap<E, Object> map; private static final Object PRESENT = new Object(); public boolean add(E e) { return map.put(e, PRESENT) == null; // 值固定 }}

使用选择建议

• 需存储关联数据 → Map

  // 用户ID到名字的映射Map<Integer, String> userNames = new HashMap<>();

• 只需检查元素存在性 → Set

  // 黑名单ID检查Set<Integer> blacklist = new HashSet<>();

三、自动拆箱与装箱

由包装类转成基本类型（如integer与int）在java5之后可以自动转换。Java 集合框架（如 HashMap）只能存储对象，所以使用包装类。
使用包装类好处：
1.可以为null值
2.有额外的扩展方法

四、为什么要使用泛型

泛型 指定键值对的类型保证类型安全，避免类型转换

五、为什么要返回一个数组前要加new

new = 拿新盒子：创建数组就像拿新盒子装东西，空盒子也需要拿（new）