首页 > > 程序设计 > Java技术 >

Two Sum - 新手上路

2019-02-17 01:51:36来源：博客园阅读 ()

不是计算机相关专业毕业的，从来没用过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 }