[leetcode]Two Sum

水の問題かと思ったら、n^2、n*log(n)からnまで最適化できた.感慨ですね~
O(n^2):暴力

public class Solution {

    public int[] twoSum(int[] numbers, int target) {

        // Start typing your Java solution below

        // DO NOT write main() function

    	int[] r = new int[2];

        for (int i = 0; i < numbers.length; i++)

        {

        	for (int j = i+1; j < numbers.length; j++)

        	{

        		if (numbers[i] + numbers[j] == target)

        		{

        			r[0] = i+1;

        			r[1] = j+1;

        			break;

        		}

        	}

        }

        return r;

    }

}

O(n*log(n):並べ替え.O(n)の空間で元の配列を記録し,最後のO(n)のスイープを開始したが,全体的な複雑さは変化しなかった.もちろんデータ構造で元と後のつながりを記録する人もいますが、それは別のO(n)の空間省が最後にスキャンしただけです.問題を解く過程で最初は元の配列を記録するのを忘れていたが、後にソートを忘れた第1、第2、ソート後も異なる可能性がある.

import java.util.Arrays;



public class Solution {

    public int[] twoSum(int[] numbers, int target) {

        // Start typing your Java solution below

        // DO NOT write main() function

        int[] result = new int[2];

    	int[] tmp = new int[numbers.length];

    	for (int i = 0; i < numbers.length; i++)

    	{

    		tmp[i] = numbers[i];

    	}

        Arrays.sort(tmp);

        int l = 0;

        int r = tmp.length - 1;

        int sum = tmp[l] + tmp[r];

        while( sum != target && r > l)

        {

        	if (sum > target)

        	{

        		r--;

        	}

        	else

        	{

        		l++;

        	}

        	sum = tmp[l] + tmp[r];

        }

        int index = 0;

        for (int i = 0; i < numbers.length; i++)

        {

        	if (tmp[l] == numbers[i] || tmp[r] == numbers[i])

        	{

        		result[index] = i + 1;

        		index++;

        		if (index > 1) break;

        	}

        }

        

        return result;

    }

}

O(n):やっぱりハシュを使っているのは不思議ではありません.したがって,実際の複雑さはHashの実現を考慮するとO(n)よりも大きくなる.

import java.util.HashMap;



public class Solution {

    public int[] twoSum(int[] numbers, int target) {

        // Start typing your Java solution below

        // DO NOT write main() function

        int[] result = new int[2];

    	HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

    	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;

    }

}