Friday, April 19, 2019

Lintcode 610. Two Sum - Difference equals to target

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.

Example

Example 1:
Input: nums = [2, 7, 15, 24], target = 5 
Output: [1, 2] 
Explanation:
(7 - 2 = 5)
Example 2:
Input: nums = [1, 1], target = 0
Output: [1, 2] 
Explanation:
(1 - 1 = 0)

Notice

It's guaranteed there is only one available solution
Code (Java):
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) {
        int[] ans = new int[2];
        
        if (nums == null || nums.length < 2) {
            return ans;
        }

        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                ans[0] = map.get(nums[i]);
                ans[1] = i + 1;
                return ans;
            }

            map.put(nums[i] + target, i + 1);
            map.put(nums[i] - target, i + 1);
        }

        return ans;
    }
}

No comments:

Post a Comment