Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2 题目的意思是 给定一个数组，要找一个出数组中两个数字之和等于特定的值target，也就是找出两个数字a，b使得a+b=target，并且假定每给定一个数组，有且仅有唯一的一组解，但是题目并没有说明数组的数字没有重复，所以也要注意考虑当数字重复的时候的情况。 思路1： 看到这个题目，我首先想到的就是两层循环遍历，先选定数组中的一个数，然后再从数组中取出数与选定的数相加，然后与target进行比较，可是时间复杂度o（n^2）太高，ac不通过。 思路2： 先将数组里面数据备份到numTemp数组中，然后将数组numbers进行排序，设置两个索引i，j，一个j从左向右开始查找，另一个i从右向左开始查找，比较如果numbers[i]+numbers[j]>target,那么将i向左移动，如果numbers[i]+numbers[j]>target，将j向右移动，如果numbers[i]+numbers[j]=target，那么需要找出numbers[i]和numbers[j]在原数组中的下标即可，但是要注意numbers[i]和numbers[j]相等和不相等时的下标方式不一样。排序的采用java提供的Arrays.sort（numbers），排序的时间复杂度为o（nlogn），然后在原数组中遍历查找下标的时间复杂度为o（n），所以整个的时间复杂度依然为o（nlogn） 代码如下：
{public int[] twoSum(int[] numbers, int target) {int sum = 0;int[] numTemp=new int[numbers.length];for(int k=0;k<numTemp.length;k++)numTemp[k]=numbers[k];int[] flag = new int[2];Arrays.sort(numbers);int i=numbers.length-1;int j=0;while(j<i){ sum = numbers[i] + numbers[j];if (sum == target) {if(numbers[i]==numbers[j]){ for(int k=0,s=numTemp.length-1;k<s;k++,s–){if(numTemp[k]==numbers[j])flag[0]=k+1;if(numTemp[s]==numbers[i])flag[1]=s+1;}}else{for(int k=0;k<numTemp.length;k++){ if(numTemp[k]==numbers[j]) flag[0]=k+1;if(numTemp[k]==numbers[i]) flag[1]=k+1;}}break;}if (sum < target)j++;if (sum > target)i–;}if(flag[0]>flag[1]){int temp=flag[1];flag[1]=flag[0];flag[0]=temp;}return flag;}}
思路3： 如果将查找a和b使得a+b=target这个问题转变一下，变成在数组中查找b使得b=target-a，也即是在数组中查找一个数是否等于给定的值，那么问题将会简单多了，，可以考虑用HashMap来存放target-a与a对应的下标，然后再遍历数组，看数组中数是否在HashMap的key中存在，若存在就取出来对应的value就是需要的下标值。遍历数组的时间复杂度为o（n），在HaspMap中查找数的时间复杂度为o(1),所以总的复杂度为o（n）。 代码如下：
public class Solution {public int[] twoSum(int[] numbers, int target) { int[] flag=new int[2];HashMap<Integer,Integer> hashTable=new HashMap<Integer,Integer>();for(int i=0;i<numbers.length;i++){if(hashTable.containsKey(numbers[i])){flag[0]=hashTable.get(numbers[i])+1;flag[1]=i+1;}elsehashTable.put(target-numbers[i], i);}return flag;}}
前有阻碍，奋力把它冲开，运用炙热的激-情，
