一道面试算法题

最新推荐文章于 2022-09-12 10:00:05 发布

*八步赶蝉*

最新推荐文章于 2022-09-12 10:00:05 发布

阅读量377

点赞数

本文链接：https://blog.csdn.net/qq_38261174/article/details/97369336

版权

本文详细解析了两数之和算法，通过使用哈希表实现了高效查找，时间复杂度和空间复杂度均为O(n)。文章提供了Java实现代码，并介绍了如何利用哈希表在一次遍历中找到目标和的两个数。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

给定一个整数数组和一个整数，返回两个数组的索引，这两个索引指向的数字的加和等于指定的整数。需要最优的算法，分析算法的空间和时间复杂度

参考答案：

//java实现，c#用字典应该也行吧
publicint[] twoSum(int[] nums,int target) {
   if(nums==null || nums.length<2)
       return new int[]{0,0};
    HashMap<Integer, Integer> map =new HashMap<Integer,Integer>();
   for(int i=0; i<nums.length; i++){
       if(map.containsKey(nums[i])){
           return new int[]{map.get(nums[i]), i};
        }else{
            map.put(target-nums[i], i);
        }
    }
    return new int[]{0,0};
}

分析：空间复杂度和时间复杂度均为 O(n)