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])
:创建一个比较器,按每行的第一个元素(即值)进行排序
分解解释
a -> a[0]
是一个lambda表达式:- 输入:
a
(代表二维数组的一行,如[3, 1]
) - 输出:
a[0]
(这行的第一个元素,即值3
)
- 输入:
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");}
}
为什么不需要排序?
哈希表解法的高效性来自于:
- 即时查找:在遍历数组时,对于每个元素,我们可以立即查询哈希表看是否已存在需要的补数
- 单次遍历:只需要遍历数组一次,O(n)时间复杂度
- 空间换时间:使用O(n)额外空间存储元素和索引的映射关系
对比你的二维数组思路:
- 哈希表法省去了O(n log n)的排序步骤
- 查找补数的时间从O(log n)(二分查找)降到了O(1)
- 整体时间复杂度从O(n log n)降到O(n)
哈希表工作流程示例
以输入nums = [2,7,11,15]
, target = 9
为例:
- 初始化空哈希表:
map = {}
- 遍历第一个元素2:
- 补数 = 9 - 2 = 7
- 7不在map中 → 存入
{2: 0}
- 遍历第二个元素7:
- 补数 = 9 - 7 = 2
- 2在map中(对应索引0)→ 返回
[0, 1]
常见疑问解答
Q: 为什么先检查补数再存入当前元素?
A: 这样可以避免使用同一个元素两次。如果先存入再查找,可能会找到自己。
Q: 如果有重复元素怎么办?
A: 题目保证只有一个解,所以即使有重复元素,正确的解也只会出现一次。哈希表会保留最后出现的索引,但解法仍然有效。
Q: 为什么用值做键,索引做值?
A: 因为我们需要快速查找某个值是否存在(用containsKey),而查找后需要获取的是它的索引(用get)。
总结
哈希表在这个问题中展现了它的强大之处:
- 通过O(1)时间复杂度的查找操作大幅提升效率
- 代码简洁明了,逻辑清晰
- 充分利用了"补数"的概念和哈希表的快速查询特性