Lintcode - 610. Two Sum - Difference equals to target

LintCode 炼码 - 更高效的学习体验！www.lintcode.com

solution1, use binary search

time: O(nlogn)

space: O(1)

public class Solution {
    /**
     * @param nums: an array of Integer
     * @param target: an integer
     * @return: [num1, num2] (num1 < num2)
     */
    public int[] twoSum7(int[] nums, int target) {
        target = Math.abs(target); // key!
        for (int i = 0; i < nums.length; i++) {
            int j = binarySearch(nums, i+1, nums.length - 1, target + nums[i]);
            if (j != -1) {
                return new int[]{nums[i], nums[j]};
            }
        }
        return new int[]{};
    }
    private int binarySearch(int[] nums, int start, int end, int target) {
        while (start + 1 < end) {
            int mid = start + (end - start)/2;
            if (nums[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (nums[start] == target) {
            return start;
        }
        if (nums[end] == target) {
            return end;
        }
        return -1;
    }
}

two pointers

time: O(n)

space: O(1)

use two pointers, same direction

public class Solution {
    /**
     * @param nums: an array of Integer
     * @param target: an integer
     * @return: [num1, num2] (num1 < num2)
     */
    public int[] twoSum7(int[] nums, int target) {
        if (nums == null || nums.length < 2) {
            return new int[]{-1,-1};
        }
        target = Math.abs(target);
        int n = nums.length;

        int j = 1;
        for (int i = 0; i < n; i++) {
            j = Math.max(j, i+1);
            while (j < n && nums[j] - nums[i] < target) {
                j++;
            }
            if (j > n) {
                break;
            }
            if (nums[j] - nums[i] == target) {
                return new int[]{nums[i], nums[j]};
            }
        }
        return new int[]{-1,-1};
    }
}