LeetCode Hot 100：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$

提示：‌

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只会存在一个有效答案

进阶：‌你可以想出一个时间复杂度小于 O(n^2) 的算法吗？

题解

首先出场的肯定是暴力穷举。

func twoSum(nums []int, target int) []int {
    for i := 0; i < len(nums) - 1; i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[i] + nums[j] == target {
                return []int{i, j}
            }
        }
    }
    return nil
}

时间复杂度O(n^2)。

然后是哈希表。

func twoSum(nums []int, target int) []int {
    hashTable := make(map[int]int)
    for i := 0; i < len(nums); i++ {
        wanted := target - nums[i]
        j, exist := hashTable[wanted]
        if exist {
            return []int{i, j}
        } else {
            hashTable[nums[i]] = i
        }
    }
    return nil
}

哈希表是标准做法。但是 Gemini 老师提出了代码上可优化的点：

func twoSum(nums []int, target int) []int {
    // 1. 预分配 map 容量
    hashTable := make(map[int]int, len(nums))
    
    // 2. 使用 for range 循环
    for i, num := range nums {
        wanted := target - num
        
        // 3. 结合 if 初始化语句，并去掉 redundant else
        if j, exist := hashTable[wanted]; exist {
            return []int{j, i} // 习惯上把小的下标/先出现的下标 j 放前面
        }
        hashTable[num] = i
    }
    return nil
}

1. 预分配map容量可以极大缩减运行时间：

   和前面聊到的切片一样，Go 的 map 在容量不足时也会发生底层的内存重新分配和哈希重哈希（Rehash）‌‌，这个过程非常耗时。

   在最坏的情况下，你可能会把 nums 里所有的元素都存进 hashTable。因此，最地道的 Go 性能优化是提前给 map 指定容量‌：

   💡 显式指定容量为 len(nums)，防止后续多次 append/insert 触发 map 扩容

   hashTable := make(map[int]int, len(nums))

   效果‌：这样写可以确保这个 map 在整个运行过程中只申请一次内存，速度达到极致。

2. 使用for range代替下标循环：

   虽然 for i := 0; i < len(nums); i++ 没有任何逻辑错误，但在 Go 语言中，更推荐使用 for range。它不仅能让代码更具可读性，还能同时优雅地拿到下标和数值：

   for i, num := range nums {

3. 拿掉多余的else：

   因为 if 分支里一旦条件满足就直接 return 结束函数了，所以在这种情况下，地道的 Go 代码会直接去掉 **else** 关键字‌，让代码少一层缩进，保持视觉上的"平铺直叙"（Go 语言官方非常推崇这种 ‌"优先处理错误/特殊情况，尽早返回"‌ 的线性代码风格）。

接下来是 Jvav 选手：

暴力：

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, 0};
    }
}

哈希表：

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

记录

1. Go 的数组长度是固定的，但是数组内容是可变的。
2. Go 中的切片和数组是完全不一样的物种；‌数组的长度是其类型的一部分‌，属于值类型；而切片是一个包含指针、长度、容量的结构体。
3. 按2中所言，Go 中的[2]int和[3]int是完全不同的类型。但是都能被[]int切片类型引用。

4. 在 Go 语言中，除了极其在乎栈内存优化且长度完全固定的场景，‌绝大多数情况下，都应该使用和返回切片（Slice）。‌

5. Go 中的map（映射）就是其他语言中的哈希表、字典（Dictionary）或关联数组，查询效率是O(1)。查询时同时返回值和是否存在。

6. Java 中的匿名变量是需要new的。

7. Java 中数组长度也是属性，所以用nums.length，而不是方法nums.length()。

8. Java 的 HashMap 属于 Java 集合框架（Collections Framework）。声明时需要使用包装类型‌（比如 Integer、String），而不能直接用基本数据类型（如 int、char）。

   Java

   import java.util.HashMap;
   import java.util.Map;
   
   // 键（Key）是 Integer，值（Value）是 Integer
   Map<Integer, Integer> map = new HashMap<>();

   注意‌：我们通常习惯用接口 Map 作为左边的类型（多态性），右边用具体的实现类 HashMap。

9. Java 的 HashMap 操作全部通过调用对象的方法来完成。