leetcode--Two Sum

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をあげて、配列の中で2つとtargetの整数を見つけます.
この2つの整数のindexを返し、index 1がindex 2より小さいことを要求します.
なお、indexは1に基づいて開始され、すなわち配列の最初のindexは0ではなく1である
分類:配列,Hash
解法1:配列が無秩序なので、考えやすい方法は並べ替えてから、頭の後ろから探すことです.
ソート後、元の要素の配列内の位置を記録するために、クラスを作成して記録します.
Javaでは自分の比較器を実現すればいいです.並べ替えアルゴリズムの時間的複雑さはO(nlogn)である.
ソート後はヘッダーの末尾から探し、ヘッダーの末尾とtargetより大きい場合は、ヘッダーの末尾が減少することを示します.targetより小さい場合は、ヘッダが大きくなります.
見つけるまでの時間的複雑さはO(n)であった.
従って全時間複雑度はO(nlogn)である

public class Solution {
    public int[] twoSum(int[] nums, int target) {
		class Num{
			int pos;
			int val;
			public Num(int pos, int val) {			
				this.pos = pos;
				this.val = val;
			}		
			
			@Override
			public String toString() {
				return val+"";
			}
		};
		
		List<Num> arr = new ArrayList<Num>();
		for(int i=0;i<nums.length;i++){
			arr.add(new Num(i,nums[i]));
		}		
		Collections.sort(arr,new Comparator<Num>() {//   
			@Override
			public int compare(Num o1, Num o2) {				
				return o1.val>o2.val?1:-1;
			}					
		});		
		ArrayList<Integer> result = new ArrayList<Integer>();
		int i=0,j=nums.length-1;
		while(i<j){//       
			if(arr.get(i).val+arr.get(j).val>target){
				j--;
			}else if(arr.get(i).val+arr.get(j).val<target){
				i++;
			}else{
				result.add(arr.get(i).pos);
				result.add(arr.get(j).pos);
				i++;j--;
			}
		}
		Collections.sort(result);
		
		int[] r = new int[result.size()];
		for(i=0;i<r.length;i++){
			r[i] = result.get(i)+1;
		}		
		return r;
    }
}

解法2:HashMapを使用して要素の位置を記録します.
配列を巡回し、現在の要素curに対してtargetでcurを減算し、hashMapでこの差が見つかるかどうかを判断します.
見つからない場合は、curとそのindexをmapに保存します.
次に次の要素を判断します.

public class Solution {
    public int[] twoSum(int[] nums, int target) {
		//   -》  
		HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
		//  ，         
		int[] result = new int[2];
		for(int i=0;i<nums.length;i++){
			if(map.get(target-nums[i])==null){//       ，    
				map.put(nums[i], i);
			}else{//      ，    
				result[0] = map.get(target-nums[i])+1;
				result[1] = i+1;
				break;
			}
		}	
		
		return result;
    }
}