算法训练之两数之和

最近开始在leetcode上开始进行刷题，并且将自己的刷题记录过程记录在博客中。

该算法的具体内容如下

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

首先看到题目是否有排序的条件，如果已经是排序好的一组数字，就可以直接利用两个指针分别指向最大数和最小数与目标数字进行比较的算法，如下所示：

//这里假定数组是按升序排列 public class Solution{ public int sum(int [] nums,int target){ int left = 0; int right = nums.length - 1; while(left < right){ if(nums[left] + nums[right] == target){ return new int[] {left , right}; break; } else if(nums[left] + nums[right] < target){left++;} else{right++} } if(left >= right) return new int[]; } }

不过这里将代码上传之后显示失败，说明数字是无序的，那么是不是可以用排序算法将数组进行排序呢，Java中提供arrays.sort()函数，可以将数组进行排序，该算法的时间复杂度是nlog2n，使用首尾指针的算法的空间复杂度是O(1)。 但是，题目要求需要对两个数的序号进行排序，sort之后就会使序号错误，于是本方法不能解决问题。 在Java中有hashmap的集合方法，其中containsKey可以利用O(1)的时间复杂度进行数字的匹配，put函数可以将数字和数字的序号进行存储，接下来看一下代码：

public class getSum{ public int[] twoSum(int[] nums , int target){ Map<Integer,Integer> map = new HashMap<>(); //map处可以定义不同种类的变量， //不过要求变量的类型是object， //于是不用int而使用integer for(int i = 0 ; i < nums.length ; i++){ int excepted = target - nums[i]; if(map.containsKey(excepted)){ return new int[] {map.get(excepted),i}; } else{ map.put(nums[i], i); } } return new int[2]; } }

这样就将题目顺利解决，接下来会给出python的解法。

题目来源：leetCode，点击访问