610.Two Sum - Difference equals to targe

1.Description(Medium)

Given an array of integers, find two numbers that theirdifferenceequals 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)

2.Code

当一个题目需要排序，但是要记录原有的index的时候需要用class Pair来同时保存下index和value.

这个题目就是需要。所以这个题目用hashmap没法做。

定住head，去遍历tail，直到找到答案。

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

    /*
     * @param nums an array of Integer
     * @param target an integer
     * @return [index1 + 1, index2 + 1] (index1 < index2)
     */
    //Solution 1:Two pointers
    public int[] twoSum7(int[] nums, int target) {
        int[] result=new int[2];
        target=Math.abs(target);//caution

        if(nums==null || nums.length<2){
            return result;
        }
        Pair[] pairs=new Pair[nums.length];
        for(int i=0;i<nums.length;i++){
            pairs[i]=new Pair(i,nums[i]);
        }
        //override the comparator
        Arrays.sort(pairs,new Comparator<Pair>(){
            public int compare(Pair a,Pair b){
                return a.val-b.val;
            }
        });

       //固定head,遍历tail
        int n=pairs.length;
        int tail=0;
        for(int i=0;i<n;i++){
            if(i==tail){
                tail++;
            }
            while(tail<n && pairs[tail].val-pairs[i].val<target){
                tail++;
            }
            if(tail<n && pairs[tail].val-pairs[i].val==target){
                if(pairs[i].index<pairs[tail].index){
                    result[0]=pairs[i].index+1;
                    result[1]=pairs[tail].index+1;
                }else{
                    result[0]=pairs[tail].index+1;
                    result[1]=pairs[i].index+1;
                }
                return result;
            }            
        }
        return result;
    }