算法题——数组（一）

1、两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

/*建一个hash表，key存放值，value存放下标
遍历数组，如果表里存在target - nums[i]，则返回下标
不存在则把当前的数存到hash表
*/
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i], i);
        }
        return new int[0];
    }
}

2、寻找两个有序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 

 1 //合并两个数组再求中位数
 2 class Solution {
 3     public double findMedianSortedArrays(int[] nums1, int[] nums2) {
 4         int len1=nums1.length,len2=nums2.length;
 5         
 6         if(len1==0&&len2%2!=0)return nums2[len2/2];
 7         if(len1==0&&len2%2==0)return ((double)nums2[len2/2]+(double)nums2[len2/2-1])/2;
 8         if(len2==0&&len1%2!=0)return nums1[len1/2];
 9         if(len2==0&&len1%2==0)return ((double)nums1[len1/2]+(double)nums1[len1/2-1])/2;
10         int[] ans=new int[len1+len2];
11         int i=0,j=0,k=0;
12         while(i<len1&&j<len2){
13             if(nums1[i]<nums2[j]){
14                 ans[k++]=nums1[i++];
15                 
16             }else{
17                 ans[k++]=nums2[j++];
18             }
19         }
20         while(i<len1){
21             ans[k++]=nums1[i++];
22         }
23         while(j<len2){
24             ans[k++]=nums2[j++];
25         }
26         int sumlen=len1+len2;
27         //return sumlen;
28         if((sumlen)%2==0)return ((double)ans[sumlen/2]+(double)ans[sumlen/2-1])/2;
29         else return ans[sumlen/2];
30 
31     }
32 }

3、盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

 1 //双指针
 2 class Solution {
 3     public int maxArea(int[] height) {
 4         int maxarea=0;
 5         int left=0,right=height.length-1;
 6         while(left<right){
 7             int area=Math.min(height[left],height[right])*(right-left);
 8             if(area>maxarea)maxarea=area;
 9             if(height[left]<height[right]){
10                 left++;
11             }else{
12                 right--;
13             }
14         }
15         return maxarea;
16     }
17 }

4、三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

 1 class Solution {
 2     public static List<List<Integer>> threeSum(int[] nums) {
 3         List<List<Integer>> ans = new ArrayList();
 4         int len = nums.length;
 5         if(nums == null || len < 3) return ans;
 6         Arrays.sort(nums); // 排序
 7         for (int i = 0; i < len ; i++) {
 8             if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
 9             if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
10             int L = i+1;
11             int R = len-1;
12             while(L < R){
13                 int sum = nums[i] + nums[L] + nums[R];
14                 if(sum == 0){
15                     ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
16                     while (L<R && nums[L] == nums[L+1]) L++; // 去重
17                     while (L<R && nums[R] == nums[R-1]) R--; // 去重
18                     L++;
19                     R--;
20                 }
21                 else if (sum < 0) L++;
22                 else if (sum > 0) R--;
23             }
24         }        
25         return ans;
26     }
27 }