LeetCode刷题【剑指 Offer 57】和为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]

限制：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^6

哈希表，双指针，二分查找

1. 哈希表
   这个哈希表有点大
   或者直接用HashSet也可以，性能甚至不如这个boolen[],我试过

class Solution {
    public int[] twoSum(int[] nums, int target) {
        boolean[] hashSet = new boolean[2000000];
        for (int num : nums) {
            if (hashSet[target-num]){
                return new int[]{num,target-num};
            }
            hashSet[num] = true;
        }
        return new int[2];
    }
}

2. 双指针
   从两边开始往中间找

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int l = 0;
        int r = nums.length-1;
        while ( l < r){
            int sum = nums[l] + nums[r];
            if(sum == target){
                return new int[]{nums[l],nums[r]};
            }
            if( sum < target){
                l++;
            }else{
                r--;
            }
        }
        return new int[]{nums[l],nums[r]};
    }
}

3. 二分

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int i = -1;
        while (++i < nums.length){
            int s = binarySearch(nums,target- nums[i]);
            if (s >= 0 && i != s){
                return new int[]{nums[i],nums[s]};
            }
        }
        return new int[2];
    }

    int binarySearch(int[] nums, int t ){
        int l = 0;
        int r = nums.length;
        while (l < r){
            int mid = l + ((r-l) >> 1);
            if (nums[mid] == t){
                return mid;
            }
            if (nums[mid] > t){
                r = mid;
            }else{
                l = mid+1;
            }
        }
        return -1;
    }
}