讨论/《画解剑指 Offer》 - 剑指 Offer 57. 和为 s 的两个数字 - 解决方案/
《画解剑指 Offer》 - 剑指 Offer 57. 和为 s 的两个数字 - 解决方案
共 1 个回复

我用的是二分法+双指针的思路,会出现用时比双指针更快的情况

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int midTarget = target >> 1;
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] <= midTarget) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if(left == right){
            right++;
        }
        while (left >= 0 && right <= nums.length - 1) {
            if (nums[left] + nums[right] == target) {
                return new int[] { nums[left], nums[right] };
            } else if (nums[left] + nums[right] > target) {
                left--;
            } else if (nums[left] + nums[right] < target) {
                right++;
            }
        }
        return new int[0];
    }
}
3