Monday, October 31, 2016

3 sum smaller


Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.
For example, given nums = [-2, 0, 1, 3], and target = 2.
Return 2. Because there are two triplets which sums are less than 2:
[-2, 0, 1]
[-2, 0, 3]
Follow up: Could you solve it in O(n2) runtime?


Similar to 3 sum. Note we need to calculate the count, so if sum <= target, total sums we can get is right - left because all pairs (left, right), (left  + 1, right) ...  (right - 1, right) together with nums[i] will lead to a sum smaller than/equal to target.

public int threeSumSmaller(int[] nums, int target) {
        if (nums.length == 0) {
            return 0;
        }
        Arrays.sort(nums);
        int count = 0;
        for (int i = 0; i + 3 <= nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum <= target) {
                    count += right - left;
                    left++;
                } else {
                    right--;
                }
                while (left < right && nums[left] == nums[left - 1]) {
                    left++;
                }
                while (left < right && nums[right] == nums[right + 1]) {
                    right--;
                }
            }
        }
        return count;
    }

No comments:

Post a Comment