Description

剑指 Offer 57. 和为s的两个数字
难度简单58收藏分享切换为英文接收动态反馈
输入一个递增排序的数组和一个数字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

    Solution

    双指针
    1. class Solution {
    2.   public int[] twoSum(int[] nums, int target) {
    3.       int left = 0,  right = nums.length-1;
    4.       int[] res = new int[2];
    5.       while(left < right){
    6.           if (nums[left] + nums[right] == target){
    7.               res[0] = nums[left];
    8.               res[1] = nums[right];
    9.               break;
    10.           }else if (nums[left] + nums[right] > target){  // 相加大于target，说明right指向的值过大
    11.               right --;
    12.           }else { //相加小于 target，说明 left 指向的值过小
    13.               left ++;
    14.           }
    15.       }
    16.       return res;
    17.   }
    18. }
    执行结果：通过
    显示详情
    执行用时：2 ms, 在所有 Java 提交中击败了97.28%的用户
    内存消耗：55.3 MB, 在所有 Java 提交中击败了84.99%的用户

可以使用二分搜索，但对于数据量小的的数组采用二分搜索的效率很低

public class Solution{
    public int[] twoSum(int[] nums, int target) {
            int a = -1, b = -1;
            for (int i = 0; i < nums.length; i ++){
                a = nums[i];
                int bi = Arrays.binarySearch(nums, i, nums.length, (target-a));
                if (bi >= i && bi < nums.length){
                    b = nums[bi];
                    break;
                }
            }
            if (a == -1 || b == -1)
                return new int[]{};
            return new int[]{a,b};
        }

        private int binarySearch(int[]nums, int lo, int hi, int target){
            while(lo <= hi){
                int mid = lo + ((hi-lo) >> 1);
                if (nums[mid] > target)
                    hi = mid - 1;
                else if (nums[mid] < target)
                    lo = mid + 1;
                else 
                    return mid;
            }
            return -1;
        }
}

执行结果：通过
显示详情
执行用时：13 ms, 在所有 Java 提交中击败了24.37%的用户
内存消耗：55 MB, 在所有 Java 提交中击败了94.73%的用户