网站建设合同缴纳印花税吗_福州短视频seo网络_百度写一篇文章多少钱_搜索关键词排名工具

1. 两数之和 - 力扣（LeetCode）

---

思路：

对数组排序能减少很多额外的计算，但是要处理好排序数组之后，能重新找到原数组对应的下标映射

---

方法一：模拟哈希表映射 + 双指针

---

class Solution {public int[] twoSum(int[] nums, int target) {int n = nums.length;int[] ret = new int[2];// 模拟哈系数组，并且存储映射关系的方法int[][] hash = new int[n][2];for(int i = 0 ; i < n ;i++){hash[i][0] = i;hash[i][1] = nums[i];}// 根据二维数组 hash 的每一个一维数组元素 hash[i] 的 hash[i][1] 大小排序Arrays.sort(hash, Comparator.comparingInt(a -> a[1]));// 使用双指针，不需要两次 for 循环int left = 0, right = n-1;while(left < right){if(hash[left][1] + hash[right][1]==target){ret[0] = hash[left][0];ret[1] = hash[right][0];// 找到元素必须马上结束循环，不然会超出时间限制break;}else if(hash[left][1] + hash[right][1] < target){left++;}else{right--;}}return ret;}
}

---

理解 Comparator.comparingInt(a -> a[0])

---

这个表达式是Java 8引入的函数式编程风格比较器，用于指定排序规则。我来详细解释它的含义和替代写法。

---

原代码解析

---

Arrays.sort(numWithIndex, Comparator.comparingInt(a -> a[0]));

• numWithIndex：二维数组，每行有两个元素 [值, 索引]
• Comparator.comparingInt(a -> a[0])：创建一个比较器，按每行的第一个元素（即值）进行排序

---

分解解释

---

1. a -> a[0] 是一个lambda表达式：
   • 输入：a（代表二维数组的一行，如 [3, 1]）
   • 输出：a[0]（这行的第一个元素，即值 3）
2. Comparator.comparingInt() 方法：
   • 接收一个"键提取函数"（这里是 a -> a[0]）
   • 返回一个根据提取的int值进行比较的Comparator

---

等效的传统写法

---

如果不使用Java 8的lambda，可以这样写：

Arrays.sort(numWithIndex, new Comparator<int[]>() {@Overridepublic int compare(int[] a, int[] b) {return Integer.compare(a[0], b[0]);}
});

---

方法二：哈希表

---

class Solution {public int[] twoSum(int[] nums, int target) {// 创建哈希表：键存储数组元素值，值存储元素索引Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {// 计算当前元素需要的补数（即target - nums[i]）int complement = target - nums[i];// 检查补数是否已经在哈希表中if (map.containsKey(complement)) {// 如果存在，返回两个索引return new int[] { map.get(complement), i };}// 将当前元素和它的索引存入哈希表map.put(nums[i], i);}// 如果没有找到解，抛出异常（根据题目描述，这种情况不会发生）throw new IllegalArgumentException("No two sum solution");}
}

---

为什么不需要排序？

---

哈希表解法的高效性来自于：

1. 即时查找：在遍历数组时，对于每个元素，我们可以立即查询哈希表看是否已存在需要的补数
2. 单次遍历：只需要遍历数组一次，O(n)时间复杂度
3. 空间换时间：使用O(n)额外空间存储元素和索引的映射关系

---

对比你的二维数组思路：

• 哈希表法省去了O(n log n)的排序步骤
• 查找补数的时间从O(log n)（二分查找）降到了O(1)
• 整体时间复杂度从O(n log n)降到O(n)

---

哈希表工作流程示例

---

以输入nums = [2,7,11,15], target = 9为例：

1. 初始化空哈希表：map = {}
2. 遍历第一个元素2：
   • 补数 = 9 - 2 = 7
   • 7不在map中 → 存入{2: 0}
3. 遍历第二个元素7：
   • 补数 = 9 - 7 = 2
   • 2在map中（对应索引0）→ 返回[0, 1]

---

常见疑问解答

---

Q: 为什么先检查补数再存入当前元素？
A: 这样可以避免使用同一个元素两次。如果先存入再查找，可能会找到自己。

---

Q: 如果有重复元素怎么办？
A: 题目保证只有一个解，所以即使有重复元素，正确的解也只会出现一次。哈希表会保留最后出现的索引，但解法仍然有效。

---

Q: 为什么用值做键，索引做值？
A: 因为我们需要快速查找某个值是否存在（用containsKey），而查找后需要获取的是它的索引（用get）。

---

总结

哈希表在这个问题中展现了它的强大之处：

1. 通过O(1)时间复杂度的查找操作大幅提升效率
2. 代码简洁明了，逻辑清晰
3. 充分利用了"补数"的概念和哈希表的快速查询特性

---