当前位置: 首页> 财经> 创投人物 > 网站建设合同缴纳印花税吗_福州短视频seo网络_百度写一篇文章多少钱_搜索关键词排名工具

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

时间:2025/7/10 12:00:06来源:https://blog.csdn.net/2402_84916296/article/details/147134824 浏览次数:0次
网站建设合同缴纳印花税吗_福州短视频seo网络_百度写一篇文章多少钱_搜索关键词排名工具

1. 两数之和 - 力扣(LeetCode)


image-20250411092026284

思路:

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


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


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. 充分利用了"补数"的概念和哈希表的快速查询特性

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

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: