leetcode算法题-01-twosum

Posted on | Edited on | In | Views:

算法第一题：

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
给一个integer类型的数组，找出其中包含的两个数字，这两个数字相加可得到指定数字。
You may assume that each input would have exactly one solution, and you may not use the same element twice.
你可以假设每个输入只有一个解决方案，而且不能使用两次相同元素。

Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

my solution我的解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] returnResult = new int[2];
        int size = nums.length;
        for(int i=0; i<size; i++){
            int firstNum = nums[i];
            
            boolean flag =false;
            for(int j= i+1; j<size; j++){
                 int secondNum = nums[j];
                 int sum = firstNum + secondNum;
                    if(sum == target){
                        returnResult[0]=i;
                        returnResult[1]=j;
                        flag =true;
                        break;
                    }
             } 
            if(flag){
                break;
            }
        }
        return returnResult;
    }
}

Runtime: 19 ms, faster than 39.98% of Java online submissions for Two Sum. 运行时间超过39.98%的提交。
Memory Usage: 38.5 MB, less than 46.13% of Java online submissions for Two Sum. 所占内存超过46.13%的提交。

Most Vote Solution投票最多的解法:
Time complexity = O(n^2);（时间复杂度大，但运行及内存使用优秀的，应该是数据量较少的原因）

1
2
3
4
5
6
7
8
9
10
11
12
13
public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> tracker = new HashMap<Integer, Integer>();
        int len = nums.length;
        for(int i = 0; i < len; i++){
            if(tracker.containsKey(nums[i])){
                int left = tracker.get(nums[i]);
                return new int[]{left+1, i+1};
            }else{
                tracker.put(target - nums[i], i);
            }
        }
        return new int[2];
    }

Runtime: 3 ms, faster than 99.30% of Java online submissions for Two Sum.
Memory Usage: 38.8 MB, less than 34.98% of Java online submissions for Two Sum.

Most Posts Solution大多数的解决方案：

Time complexity:
step1 : copy an array, and sort it using quick sort, O(nlogn)
step2 : using start and end points to find a, b which satifys a+b==target, O(n)
step3 : find the index of a, b from origin array, O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public int[] twoSum_n2(int[] nums, int target) {
    	if(nums == null)
    		return null;
    	int[] nums2 = Arrays.copyOf(nums, nums.length);
    	Arrays.sort(nums2);
    	int a = 0, b = 0;
    	int start = 0, end = nums2.length-1;
    	//find two nums
    	while(start<end){
    		int sum = nums2[start] + nums2[end];
    		if(sum < target)
    			start++;
    		else if(sum > target)
    			end--;
    		else{
    			a = nums2[start]; b = nums2[end];
    			break;
    		}
    	}
    	//find the index of two numbers
    	int[] res = new int[2];
    	for(int i = 0; i < nums.length; i++){
    		if(nums[i] == a){
    			res[0] = i;
    			break;
    		}
    	}
    	if(a != b){
    		for(int i = 0; i < nums.length; i++){
	    		if(nums[i] == b){
	    			res[1] = i;
	    			break;
	    		}
	    	}
    	} else{
    		for(int i = 0; i < nums.length; i++){
	    		if(nums[i] == b && i != res[0]){
	    			res[1] = i;
	    			break;
	    		}
	    	}
    	}
    	
    	return res;
    }

Runtime: 3 ms, faster than 99.30% of Java online submissions for Two Sum.
Memory Usage: 39 MB, less than 28.65% of Java online submissions for Two Sum.

看了第三种应该在大数据量运算的时候更加优秀，Arrays.copyOf好在哪？