[LintCode] 610 Two Sum - Difference equals to target 解题报告

Description
Given an array of integers, find two numbers that their difference equals to a target value.
where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are NOT zero-based.


Notice
It's guaranteed there is only one available solution



Example
Given nums = [2, 7, 15, 24], target = 5
return [1, 2] (7 - 2 = 5)




思路
排序以后两个指针同时从左往右走。



Code

class Pair {
    int val;
    int idx;
    public Pair(int val, int idx) {
        this.val = val;
        this.idx = idx;
    }
}

public class Solution {
    /*
     * @param nums an array of Integer
     * @param target an integer
     * @return [index1 + 1, index2 + 1] (index1 < index2)
     */
    public int[] twoSum7(int[] nums, int target) {
        // write your code here
        
        target = Math.abs(target);
        int[] result = new int[2];
        
        Pair[] pairs = new Pair[nums.length];
        for (int i = 0; i < nums.length; i++) {
            pairs[i] = new Pair(nums[i], i);
        }
        
        Arrays.sort(pairs, new Comparator<Pair>() {
            public int compare(Pair x, Pair y) {
                return x.val - y.val;
            }
        });
        
        
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (j == i) {
                j++;
            }
            
            while (j < nums.length && pairs[j].val - pairs[i].val < target) {
                j++;
            }
            
            if (j < nums.length && pairs[j].val - pairs[i].val == target) {
                result[0] = Math.min(pairs[i].idx, pairs[j].idx) + 1;
                result[1] = Math.max(pairs[i].idx, pairs[j].idx) + 1;
                return result;
            }
        }
        
        return result;
    }
}