LeetCode 259. 3Sum Smaller

The most intuitive way is that, using three pointers. FIrst we need to sort the array by ascending order. We set two numbers to be fixed at every iteration, and then use the first pointer to traverse all the numbers behind them, to compare their sum with target. And move the second pointer one step to the right, traverse numbers using the first pointer agian. When the second pointer finishes traversing, move the third pointer one step forward…
This is time consuming, which is not a good option.

解法一

思路

We can reduce the problem to a twoSumSmaller question. num[i] + num[j] + num[k] < target can be reduced to find all pairs satisfying num[j] + num[k] < target - num[i].

Set two pointers i, j at beginning index and end of the sorted array respectively.
Initialize the sum = 0; // Count all pairs.
While j < k
    compare nums[j] + nums[k] with new target (which is target - num[i]);
        if nums[j] + nums[k] is larger or equal to ...,
            move pointer k to the left by one step to make nums[k] smaller;
        else
            add all pairs (k - j) to sum;
            move j one step forward;
return sum;

And to solve three sum smaller, for each nums[i], we set the target to be target - nums[i], and solve the two sum smaller subproblem starting at i + 1 index. Traverse each nums[i] till nums[len - 3] to avoid the overflow when solving two sum smaller problem at the end of the array.

代码
class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        int len = nums.length;
        if (len == 0 || nums == null) return 0;
        Arrays.sort(nums);
        int sum = 0;
        for (int i = 0; i < len - 2; i++) {
            // To find how many pairs satisfy nums[i] + nums[j] + nums[k] < target,
            // is acctually finding how many pairs satistying nums[j] + nums[k] < target - nums[i]
            // for each nums[i].
            sum += twoSumSmaller(nums, i + 1, target - nums[i]);
        }
        return sum;
    }

    // Two pointers to check how many pairs satisfy the constraint.
    public int twoSumSmaller(int[] nums, int startIndex, int target) {
        int sum = 0;
        int i = startIndex;
        int j = nums.length - 1;
        while (i < j) {
            if (nums[i] + nums[j] >= target) {
                j--;
            } else {
                sum+= j - i;
                i++;
            }
        }
        return sum;
    }
}
复杂度分析
  • 时间复杂度
    排序花费 O(nlog(n)), twoSumSmaller 花费 O(n), threeSumSmaller 花费 O(n) * O(n) + O(nlog(n));
    所以时间复杂度为 O(n^2).
  • 空间复杂度
    O(1)

解法二

思路

The same as the first solution, we reduce the problem to a sumSumSmaller problem. The different approach is that, when nums[j] is fixed, to find the left largest number nums[k] such that their sum is just less than target, we do a binary search for it. And then caluculate the total pairs by k - j.

代码
class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        if (nums.length == 0 || nums == null) return 0;
        Arrays.sort(nums);
        int len = nums.length;
        int sum = 0;
        for (int i = 0; i < len; i++) {
            sum += twoSumSmaller(nums, i + 1, target - nums[i]);
        }
        return sum;
    }

    public int twoSumSmaller(int[] nums, int startIndex, int target) {
        int sum = 0;
        for (int j = startIndex; j < nums.length; j++) {
                int k = binarySearch(nums, i, target - nums[j]);
                sum += k - j;
        }
        return sum;
    }

    public int binarySearch(int[] nums, int startIndex, int target) {
        int left = startIndex;
        int right = nums.length - 1;
        while (left < right) {
            int mid = (right - left + 1)/2 + left;
            if (nums[mid] < target) {
                left = mid;
            } else {
                right = mid - 1;
            } 
        }
        return left;
    }
}
复杂度分析
  • 时间复杂度
    O(n * nlogn) = O(n^2 * logn)
  • 空间复杂度
    O(1)

Takeaway

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!