leetcode-java题解（每天更新）

说明：选用java，重在体会，性能不是最优。欢迎转载：http://www.ming-yue.cn/leetcode-java-solutions/。

先给出一个leetcode的已有答案，为什么上来直接给出答案，因为这个好多答案写的都非常简洁，不太易懂，还是建议先自己做，答案只是参考http://www.ninechapter.com/solutions/。

1，https://leetcode.com/problems/two-sum/，题目大意是给出一个无序的数组和一个目标值，假设数组里有且只有两个数相加和目标值相等，按索引由小到大输出这两个数字的索引，从1开始索引。

思路：既然题目假设有两个数a,b肯定相加得到目标值c，那么肯定有c-a存在于数组中，于是问题转化成了如何高效检查一个数组中是否包含某个值，在这里找到一些答案http://www.diguage.com/archives/112.html。于是采用先排序，然后用Arrays.binarySearch的方法，然后根据OJ提示的一些错误，修改几下就好了。具体代码如下，254ms，和九章以及其他解题答案不太一样。

import java.util.Arrays;

public class Solution1 {
	 public static int[] twoSum(int[] numbers, int target) 
	 {
	    	int[] num = numbers.clone();
	    	Arrays.sort(num);
	        int size = num.length;
	        int[] answers = new int[2];
	        for(int i=0;i<size;i++)
	        {
	        	if(Arrays.binarySearch(num, target-num[i])>0)
	        	{
	        			int count=0,index1 = 0,index2=0;
	        			for(int j=0;j<size;j++)
	        			{
	        				if(numbers[j]==num[i]||numbers[j]==target-num[i])
	        				{
	        					count++;
	        					if(count==2)
	        					{
	        						index2=j;
	        						answers[0] = (index1<index2?index1:index2)+1;
	        		        		answers[1] = (index1>index2?index1:index2)+1;
	        						break;
	        					}
	        					else 
	        					{
	        						index1=j;
								}
	        					
	        				}
	        			}
	        		
	        		
	        	}
	        }
	        return answers;
	    }
	    public static void main(String[] args) 
	    {
			int[] test = {-3,4,3,90};
			int target = 0;
			int[] result = {0,0};
			result = twoSum(test,target);
			System.out.println(result[0]+","+result[1]);
		}
}

2，https://leetcode.com/problems/median-of-two-sorted-arrays/，题目大意是有两个有序数组AB，长度mn，求出这两个数组的中位数，log（m+n）。分两种思路，一是先归并成C，再求中位数；二是分别求出AB的中位数，利用二分查找找出最终结果，中位数的概念http://zh.wikipedia.org/wiki/%E4%B8%AD%E4%BD%8D%E6%95%B8。

我先用第一种容易理解的方式AC，答案比较简单：

	//solution1:先归并合并，再求中位数
	  public static double findMedianSortedArrays(int A[], int B[]) {
        int[] C= mergeSortSub(A, B);
        double result=0;
        int n=C.length;
        
        if(n%2==0)
        {
        	double m1=0.5*n-1;
        	double m2=0.5*n;
        	result = 0.5*(C[(int) m1]+C[(int) m2]);
        }else {
			result = C[(int) Math.round(0.5*n-1)];
		}
        return result;
    }
	
	 
	private static int[] mergeSortSub(int[] arr1,int[] arr2){//归并排序子程序
		if(arr1.length==0)
		{
			return arr2;
		}
		if(arr2.length==0)
		{
			return arr1;
		}
		int[] result = new int[arr1.length+arr2.length];
		int i = 0;
		int j = 0;
		int k = 0;
		while(true){
			if(arr1[i] < arr2[j]){
				result[k] = arr1[i];
				if(++i>arr1.length-1){
					break;
				}
			}else{
				result[k] = arr2[j];
				if(++j>arr2.length-1){
					break;
				}
			}
			k++;
		}
		for(;i<arr1.length;i++){
			result[++k] = arr1[i];
		}
		for(;j<arr2.length;j++){
			result[++k] = arr2[j];
		}
		return result;
	}
	public static void main(String[] args) {
		int A[]={1,2,3,4};
		int B[]={5,6,7,8};
		double result = findMedianSortedArrays(A,B);
		System.out.println(result);
	}

答案2就是参考的九章里面的解法，读懂然后过一段时间默写。

3，https://leetcode.com/problems/longest-substring-without-repeating-characters/，题目大意就是找出一个字符串中不重复的最长子串。

这个比较简单，想清楚关键一点就是判断出重复后，从重复字符的下一索引继续开始，不要遗漏。

代码如下：

public class Solution3 {
    public static int lengthOfLongestSubstring(String s) {
        int len = s.length();
        if(len==0)
        {
        	return 0;
        }
        String string = null;
        String subString = null;
        int maxLength = 0;
        for(int i=0;i<len;i++)
        {
        	subString = String.valueOf(s.charAt(i));
        	if(i==0)
        	{
            	string = subString;
            	subString = null;
        	}else 
        	{
				if(!string.contains(subString))
				{
					
					subString = string+subString;
					string = subString;
					if(string.length()>maxLength)
					{
						maxLength = string.length();
					}
					subString = null;
				}else 
				{
					int index = string.indexOf(subString);
					subString = string.substring(index+1)+subString;
					string = subString;
					if(string.length()>maxLength)
					{
						maxLength = string.length();
					}
					subString = null;
				}
			}
        	
        }
		return maxLength;
    }
    
    public static void main(String[] args) {
		String string = "dvdf";
		int result = lengthOfLongestSubstring(string);
		System.out.println(result);
	}
}