Two Sum Closest (Ladder)

Description

Given an array nums of n integers, find two integers in nums such that the sum is closest to a given number, target.

Return the difference between the sum of the two integers and the target.

Example
Given array nums = [-1, 2, 1, -4], and target = 4.

The minimum difference is 1. (4 - (2 + 1) = 1).

Challenge
Do it in O(nlogn) time complexity.

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

   class Solution {
   public:
    /**
     * @param nums an integer array
     * @param target an integer
     * @return the difference between the sum and the target
     */
    int twoSumCloset(vector<int>& nums, int target) {
        // Write your code here
        if (nums.empty()) {
            return -1;
        }
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int diff = INT_MAX;
        int i = 0;
        int j = n-1;
        while (i < j) {
            if (nums[i] + nums[j] < target) {
                diff =  min(diff, abs(target - nums[i] - nums[j]));
                i++;
            } else if (nums[i] + nums[j] > target) {
                diff =  min(diff, abs(nums[i] + nums[j] - target));
                j--;
            } else {
                diff = 0;
                break;
            }
        }
        return diff;
    }
   };
   

Similar problems

x

Tags

x