Python编程实践操作教程:两数之和—Java和Python的代码对比

Python编程实践操作教程:两数之和,分别用Java和Python表现!伙伴们可以做个对比!

达坂城网站建设公司成都创新互联,达坂城网站设计制作,有大型网站制作公司丰富经验。已为达坂城上千余家提供企业网站建设服务。企业网站搭建\外贸营销网站建设要多少钱,请找那个售后服务好的达坂城做网站的公司定做!

题目:

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

Python编程实践操作教程:两数之和—Java和Python的代码对比

示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题思路:

  • 暴力穷举:外循环遍历每个元素 x,内循环查找是否存在一个值与 target - x 相等的目标元素,返回相等的目标元素和 x 的索引。时间复杂度 O (n^2),效率太低,pass。

哈希表:哈希映射(map、dict),key 保存该元素,value 保存该元素索引。

  • 两次遍历法:第一次遍历把所有元素及其索引保存到哈希映射,第二次遍历查找 target - x 相等的目标元素
  • 一次遍历法:假如 y = target - x,则 x = target -y,所以一次遍历 在存入哈希映射的同时查找是否存在一个值与 target - x 相等的目标元素。
例:nums = [2, 11, 7, 15], target = 9, hashmap = { }
遍历:
i = 0: target - x = 9 - 2 = 7, 7 不存在于 hashmap 中,则 x(2) 加入 hashmap, hashmap = {2 : 0}
i = 1: target - x = 9 - 11 = -2, -2 不存在于 hashmap 中,则 x(-2) 加入 hashmap, hashmap = {2 : 0, 11 : 1}
i = 2: target - x = 9 - 7 = 2, 2 存在于 hashmap 中,则返回列表 [2, 0]

代码:

两次遍历(Java):

class Solution {
 public int[] twoSum(int[] nums, int target) {
 Map map = new HashMap<>();
 for (int i = 0; i < nums.length; i++) {//一次遍历转换成键值对,key为元素值,value为索引值
 map.put(nums[i], i);
 }
 for (int i = 0; i < nums.length; i++) {//二次遍历查找符合条件的元素
 int res = target - nums[i];
 if (map.containsKey(res) && map.get(res) != i) {//查找到的目标元素不能为其本身
 return new int[]{i, map.get(res)};
 }
 }
 return null;
 }
}

一次遍历 (Java):

class Solution {
 public int[] twoSum(int[] nums, int target) {
 Map map = new HashMap<>();
 for (int i = 0; i < nums.length; i++) {
 int res = target - nums[i];
 if (map.containsKey(res)) {//因为自身元素还未加入到 hashmap,无需 map.get(res) != i 条件判断
 return new int[]{i, map.get(res)};
 }
 map.put(nums[i], i);//未找到目标元素则将其加入 hashmap
 }
 return null;
 }
}

一次遍历 (Python):

class Solution:
 def twoSum(self, nums: List[int], target: int) -> List[int]:
 dic = {}
 for i, num in enumerate(nums): #枚举 nums 数组
 if num in dic:
 return [dic[num], i]
 else:
 dic[target-num] = i

利用 Python 数组自带 index 方法解题:

class Solution:
 def twoSum(self, nums: List[int], target: int) -> List[int]:
 for i, num in enumerate(nums):
 if target-num in nums and nums.index(target-num) != i:
 return [i, nums.index(target-num)]

list.index():

描述:

index () 函数用于从列表中找出某个值第一个匹配项的索引位置。

语法:

index () 方法语法:

list.index(x, start, end)

参数:

  • x-- 查找的对象。
  • start-- 可选,查找的起始位置。
  • end-- 可选,查找的结束位置。

返回:

该方法返回查找对象的索引位置,如果没有找到对象则抛出异常。

有不清楚的地方可以留言或者私信!


文章题目:Python编程实践操作教程:两数之和—Java和Python的代码对比
网页URL:http://scyanting.com/article/goccii.html