LeetCodeブラシ問題記録Two Sum

2599 ワード

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.
考え方:
元の配列をコピーしてソートします.ソート後の配列でこの2つの数を探します.最後に、元の配列でこの2つの数字のindexを探せばいいです.
時間複雑度O(nlogn)+O(n)+O(n)=O(nlogn)
0 3 4 0、0は1と4を返し、1と1または4と4を返さないでください.
コード:
	public int[] twoSum(int[] numbers, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function
		
		//Copy the original array and sort it
		int N = numbers.length;
		int[] sorted = new int[N];
		System.arraycopy(numbers, 0, sorted, 0, N);
        Arrays.sort(sorted);
        //find the two numbers using the sorted arrays
        int first = 0;
        int second = sorted.length - 1;
        while(first < second){
        	if(sorted[first] + sorted[second] < target){
        		first++;
        		continue;
        	}
        	else if(sorted[first] + sorted[second] > target){
        		second--;
        		continue;
        	}
        	else break;
        }
        int number1 = sorted[first];
        int number2 = sorted[second];
        //Find the two indexes in the original array
        int index1 = -1, index2 = -1;
        for(int i = 0; i < N; i++){
        	if((numbers[i] == number1) || (numbers[i] == number2)){
        		 if(index1 == -1)
        			 index1 = i + 1;
        		 else
        			 index2 = i + 1;
        	}
        		
        }
        int [] result = new int[]{index1, index2};
        Arrays.sort(result);
		return result;
    }

hashmapのO(n)を恥知らずに利用するアルゴリズムもあり、原理と暴力検索には本質的な違いはないが、hashmapの検索速度はO(1)である.
public int[] twoSum(int[] numbers, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		int n = numbers.length;
		int[] result = new int[2];
		for (int i = 0; i < numbers.length; i++)
        {
            if (map.containsKey(target - numbers[i]))
            {
                result[0] = map.get(target-numbers[i]) + 1;
                result[1] = i + 1;
                break;
            }
            else
            {
                map.put(numbers[i], i);
            }
        }
		return result;
        
    }