【leetcode系列】Two Sum

雨点打透心脏的1/2处 2022-08-10 16:39 85阅读 0赞

解法一，我自己想的，有点弱，时间复杂度O(n^2)。

public class Solution {
    	public int[] twoSum(int[] numbers, int target) {
    		int[] result = 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) {
    					result[0] = i;
    					result[1] = j;
    				}
    			}
    		}
    		if (result[0] == 0) {
    			if (result[1] != 1) {
    				int tmp = numbers[0];
    				numbers[0] = numbers[1];
    				numbers[1] = tmp;
    				result[0] = 1;
    			} else {
    				int tmp = numbers[1];
    				numbers[1] = numbers[2];
    				numbers[2] = tmp;
    				result[1] = 2;
    				tmp = numbers[0];
    				numbers[0] = numbers[1];
    				numbers[1] = tmp;
    				result[0] = 1;
    			}
    		}
    		return result;
    	}
    
    	public void arrayPrint(int[] array) {
    		for (int i = 0; i < array.length; i++) {
    			System.out.print(array[i] + " ");
    		}
    		System.out.println();
    	}
    
    	public static void main(String[] args) {
    		int[] numbers = { 11, -22, 12, 7, 2 };
    		int target = 9;
    		Solution mSolution = new Solution();
    		mSolution.arrayPrint(numbers);
    		int[] result = mSolution.twoSum(numbers, target);
    		mSolution.arrayPrint(result);
    		mSolution.arrayPrint(numbers);
    	}
    }

解法二，网上大牛的， [点击打开链接][Link 1]，很巧妙，用java的hashtable，典型的空间换时间，时间复杂度O(n)，但是要满足下标的要求，必须在找出满足条件的数字后再重新排个序，下面是我稍微修改的代码：

public int[] twoSum_2(int[] numbers, int target) {
    	int[] result = new int[2];
    	HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
    	for(int i = 0; i < numbers.length; i++) {
    		if(hm.get(target - numbers[i]) != null) {
    			result[0] = hm.get(target - numbers[i]);
    			result[1] = i;
    		} else {
    			hm.put(numbers[i], i);
    		}
    	}
    	if (result[0] == 0) {
    		if (result[1] != 1) {
    			int tmp = numbers[0];
    			numbers[0] = numbers[1];
    			numbers[1] = tmp;
    			result[0] = 1;
    		} else {
    			int tmp = numbers[1];
    			numbers[1] = numbers[2];
    			numbers[2] = tmp;
    			result[1] = 2;
    			tmp = numbers[0];
    			numbers[0] = numbers[1];
    			numbers[1] = tmp;
    			result[0] = 1;
    		}
    	}
    	return result;
    }

[Link 1]: http://blog.csdn.net/fightforyourdream/article/details/13013147