day43(5.20)

1. 和为s的两个数字

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]
示例 2：
输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]

思路：

• 创建一个HashMap，将数组中所有所有数以k|v，target - nums[i] | nums[i] 存入。

• 循环：

  • 判断是否含有key = num[i]
    • 如果存在，返回数组，元素为[key, value]

• 优化思想：

  • 数组中元素>target, 则不需要进行存储，循环判断时候也不需要进行。

    class Solution {
    public int[] twoSum(int[] nums, int target) {
       Map<Integer,Integer> map = new HashMap<>();
       int i = 0;
       while(i<nums.length&&nums[i]<=target){
           if(map.containsKey(nums[i])){
               int[] res = {nums[i],map.get(nums[i])};
               return res;
           }
           map.put(target-nums[i],nums[i]);
           i++;
       }
       return null;
    }
    }
    

• 速度慢，内存消耗也高。

优秀解法：

• 双指针配对
  • 如果之和>target，右指针左移
  • 如果之和<target，左指针右移

    class Solution {
    public int[] twoSum(int[] nums, int target) {
       int left = 0;
       int right = nums.length-1;
       while(nums[right]>target){
           right--;
       }
       while(left<right){
           if(nums[left]+nums[right] == target){
               int[] res = {nums[left],nums[right]};
               return res;
           }else if(nums[left]+nums[right] > target){
               right--;
           }else{
               left++;
           }
       }
       return null;
    }
    }