LeetCode--数组专题

 1         // 部分基本类型
 2         int[] ints = {1, 2, 3, 4};
 3         double[] doubles = {1.0, 2.0, 3.0};
 4         
 5         // 部分引用数据类型
 6         String[] strings = {"my", "name", "is", "peanut"};
 7         Object object1 = new Object();
 8         Object object2 = new Object();
 9         Object object3 = new Object();
10         
11         Object[] objects = {object1, object2, object3};

 1 class Solution {
 2     public int[] twoSum(int[] nums, int target) {
 3         // 用 HashMap 来装下找到数组元素及其下标
 4         Map<Integer, Integer> map = new HashMap<>();
 5         
 6         // 遍历数组，将key-->nums[i], value-->i, 装进HashMap中
 7         // 其实不用全部装，可以将循环体内代码放到下一个for-loop中
 8         // for (int i = 0; i < nums.length; i++) {
 9         //     map.put(nums[i], i);
10         // }
11         
12         // 检验是否有符合条件的元素，有就返回
13         for (int i = 0; i < nums.length; i++) {
14             int result = target - nums[i];
15             map.put(nums[i], i);
16             // 要保证重复返回用一个下标的情形，例如 4+4=8，返回两次元素4的下标
17             if (map.containsKey(result) && map.get(result) != i) {
18                 return new int[] {i, map.get(result)};
19             } 
20         }
21         // 如果找不到返回错误
22         throw new IllegalArgumentException("No two sum solution");
23     }
24 }

 1 class Solution {
 2     public double findMedianSortedArrays(int[] nums1, int[] nums2) {
 3         int m = nums1.length;
 4         int n = nums2.length;
 5         
 6         // 有上面的思路可知，将长度小的数组放到前面，会快一点找到目标元素
 7         if (m > n) {
 8             int[] temp = nums1;
 9             nums1 = nums2;
10             nums2 = temp;
11             
12             int tmp = m;
13             m = n;
14             n = tmp;
15         }
16         
17         int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
18         while (iMin <= iMax) {
19             // 确定划分的长度
20             int i = (iMin + iMax) / 2;
21             int j = halfLen - i;
22             if (i < iMax && nums2[j - 1] > nums1[i]) {
23                  // i小了，将目标值往后面寻找
24                 iMin = i + 1;
25             } else if (i > iMin &&  nums1[i-1] > nums2[j]) {
26                  // i大了，将目标值往前面寻找
27                 iMax = i - 1;
28             } else {
29                 // 找到了合适i，需要知道的是，当i在移动时，j同样在移动，
30                 int maxLeft = 0;
31                 if (i == 0) {
32                     // 极端情况：数组1元素移动到开头后，此时 j=halfLen，则返回nums2[j-1]
33                     maxLeft = nums2[j-1];
34                 } else if (j == 0) {
35                     // 极端情况:i一直往右移，当j=0时，需要达成的条件为i=halfLen,
36                     // 此时需要明白，需要两个数组的长度一样才能达到上述条件，
37                     // 此时说明数组1中的元素均小于数组2的任意元素
38                     maxLeft = nums1[i-1];
39                 } else {
40                     // 在数组1和数组2之间选择一个作为左边最大
41                     maxLeft = Math.max(nums2[j-1], nums1[i-1]);
42                 }
43                 // 校验元素的个数是不是奇数
44                 if ((m+n) % 2 == 1) {
45                     return maxLeft;
46                 }
47                 
48                 int minRight = 0;
49                 if (i == m) {
50                     // 极端情况：数组1元素移到了最右边，说明需要选定的右半部分的最小值为nums2[j]
51                     minRight = nums2[j];
52                 } else if (j == n) {
53                     // 极端情况：因为长度小的数组放在前面，若是j=n，则说明n-m <= 1,
54                     // 此外，需要数组1的任意元素都要大于数组2的元素
55                     minRight = nums1[i];
56                 } else {
57                     // 在数组1和数组2之间选择一个作为右边最小
58                     minRight = Math.min(nums2[j], nums1[i]);
59                 }
60                 return (maxLeft + minRight) / 2.0;
61             }
62         }
63         return 0.0;
64     }
65 }