Two Sum - 新手上路

不是電腦相關專業畢業的，從來沒用過leetcode，最近在學習數據結構和演算法，用leetcode練練手。

新手上路，代碼如有不妥之處，儘管指出來。

今天抽空做的第一個題：Two Sum（最簡單的呃呃呃）

題目如下：

　　解決思路：

　　現有數組nums[p-r]，首先將nums從小至大排序，然後將nums[p] + nums[r]與指定值k比較，如果nums[p] + nums[r] > k則說明nums[r]大了，r--；

反之p++，直到nums[p] + nums[r] = k。

　　以下是我的Java實現（老實說，時間複雜度較高）

 1 class Solution {
 2     public int[] twoSum(int[] nums, int target) {
 3         int[] copyNums = new int[nums.length];
 4         for(int i = 0; i < nums.length; ++i){
 5             copyNums[i] = nums[i];
 6         }
 7         int[] result = new int[2];
 8         
 9         // 先排序
10         quickSort(nums, 0, nums.length - 1);
11         
12         // 將兩個元素之和與target相比較
13         int[] temp = compare(nums, 0, nums.length - 1, target);
14         
15         boolean flagA = false;
16         boolean flagB = false;
17         for(int i = 0; i < copyNums.length; ++i){
18             if(temp[0] == copyNums[i] && !flagA){
19                 result[0] = i;
20                 flagA = true;
21                 continue;
22             }
23             if(temp[1] == copyNums[i] && !flagB){
24                 result[1] = i;
25                 flagB = true;
26             }
27         }
28         return result;
29     }
30     
31     private int[] compare(int[] nums, int p, int r, int target){
32         while(p < r){
33             int k = nums[p] + nums[r];
34             if(k == target)
35                 return new int[]{nums[p], nums[r]};
36             if(k > target){
37                 r--;
38             }else{
39                 p++;
40             }
41         }
42         return null;
43     }
44     
45     private void quickSort(int[] nums, int p, int r){
46         if(p >= r)
47             return;
48         int q = partition(nums, p, r);
49         quickSort(nums, p, q-1);
50         quickSort(nums, q+1, r);
51     }
52     
53     private int partition(int[] nums, int p, int r){
54         // 最簡單的，選擇nums最後一個元素作為中間數
55         int k = nums[r];
56         int i = p;
57         
58         for(int j = p; j <= r; j++){
59             if(nums[j] < k){
60                 int temp = nums[i];
61                 nums[i] = nums[j];
62                 nums[j] = temp;
63                 ++i;
64             }
65         }
66         
67         nums[r] = nums[i];
68         nums[i] = k;
69         
70         return i;
71     }
72 }