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.有额外的扩展方法

四、为什么要使用泛型

泛型 <K,V> 指定键值对的类型 保证类型安全，避免类型转换

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

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