Array Four

(1)Two Sum

解题思路：

使用hashmap,将（目标和-当前元素值，当前元素位置）存入，当遇到（目标和-当前元素值）的值时，取出i即可。

 1 public class Solution {
 2     public int[] twoSum(int[] nums, int target) {
 3         HashMap<Integer,Integer> map = new HashMap<>();
 4         for (int i = 0; i < nums.length; i++) {
 5             if (map.get(nums[i]) != null) {
 6                 int[] result = {map.get(nums[i]), i};
 7                 return result;
 8             }
 9             map.put(target - nums[i], i);
10         }
11         int[] result= {};
12         return result;
13     }
14 }

View Code

注意map.get 和map.put的使用

(2)414. Third Maximum Number

代码如下：

 1 public class Solution {
 2     public int thirdMax(int[] nums) {
 3         int max, mid, min, count, t;
 4         max = mid = min =Integer.MIN_VALUE;
 5         count = 0;
 6         t = 0;
 7         for (int i = 0; i < nums.length; i++) {
 8             if (nums[i] == Integer.MIN_VALUE) {
 9                 t = 1;
10             }
11             if (nums[i] > max) {
12                 min = mid;
13                 mid = max;
14                 max = nums[i];
15                 count++;
16             } else if (nums[i] > mid && nums[i] < max) {
17                 min = mid;
18                 mid = nums[i];
19                 count++;
20             } else if (nums[i] > min && nums[i] < mid) {
21                 min = nums[i];
22                 count++;
23             }
24         }
25         if (count < 2 || (count == 2 && t == 0)) {
26             return max;
27         } else {
28             return min;
29         }
30     }
31 }

View Code

解题思路：

注意[1,-2147483648,2]和[1,2]这两种情况下，max都是2，second都是1，third都是-2147483648。但是前者应该输出-2147483648，后者应该输出2。所以需要t标志位来确定数组中是否出现-2147483648。count用于计数寻找到前三大数字中的几个。如果小于2直接输出最大值；如果等于2 且数组中没有出现-2147483648，输出最大值；其余情况输出最小值。

(3)Rotate Array

代码如下：

 1 public class Solution {
 2     private void reverse(int[] nums, int start, int end) {
 3         while (start < end) {
 4             int temp = nums[start];
 5             nums[start] = nums[end];
 6             nums[end] = temp;
 7             start++;
 8             end--;
 9         }
10     }
11     public void rotate(int[] nums, int k) {
12         if (nums.length == 0) {
13             return;
14         }
15         k = k % nums.length;
16         //Time Limit Exceeded
17     //reverse(nums, 0, nums.length - 1);
18         //reverse(nums, 0, k - 1);
19         //reverse(nums, k, nums.length - 1);
20     //Accepted
21     reverse(nums, 0, nums.length - k - 1);
22         reverse(nums, nums.length - k, nums.length - 1);
23         reverse(nums, 0, nums.length - 1);
24     }
25 }

View Code

解题思路：

先将k转换成[0, n-1]内的数。先对[0, k]位置的数字进行反转，再对剩下的部分进行翻转，最后对整个数组进行翻转。

若先对整个数组进行翻转，再对[0, k-1]位置的数字进行反转，最后对剩下的部分进行翻转，就会时间超限！！！【原因未知】