題目

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

思路

剛開始，我是直接一個一個的比的，復雜度是n^2 結果是超時..但是我看到了用C++的，也是和我的思路一樣的居然可以通過，也是n^2.

頓時無語

然後看了看了那個PDF（就是LeetCode題目類型分析），發現是考排序..

好

用JAVA的Collections的sort()，復雜度是nlogn..

然後就是排好序的東西了，通過雙指針來查找

本來我是直接對那個numbers數組排序，然後查找。最終是可以找到對應的位置，可是，此時的numbers已經改變了.所以我用一個Node節點來維護位置和數值

代碼

class Node implements Comparable
{
	private int index;
	private int value;
	
	public Node(int index,int value)
	{
		this.index = index;
		this.value = value;
	}
	
	public int getIndex()
	{
		return index;
	}
	
	public int getValue()
	{
		return value;
	}

	@Override
	public int compareTo(Node node)
	{
		 
		return (this.value >node.value)?1:-1;
	}
}
public class Solution {
    public int[] twoSum(int[] numbers, int target) {
	        int [] result = new int[2];

	        List list = new ArrayList();
	        
	        for ( int i = 0 ; i < numbers.length ; i++)
	        {
	        	list.add(new Node(i+1,numbers[i]));
	        }
	        
	        
	        Collections.sort(list);
	        int min = 0;
	        int max = numbers.length-1;

	        
	        while(min < max)
	        {
	        	if( list.get(min).getValue()+list.get(max).getValue()  target)
	        	{
	        		max--;
	        	}
	        	else 
	        		break;
	        }
	        
	        result[0] = (list.get(min).getIndex()>list.get(max).getIndex())?list.get(max).getIndex():list.get(min).getIndex();//確保第一個數小於第二個數
	        result[1] = (list.get(min).getIndex()>list.get(max).getIndex())?list.get(min).getIndex():list.get(max).getIndex();
	        return result;
    }
}