LeetCode 259. Three Sum Smaller

解法一 转化为 Two Sum 问题

思路

先将数组进行排序。对于每一个元素nums[i]，寻找位于该元素后的所有 sum 小于 target - nums[i] 的数对。如何计算个数？

举个例子：[1,3,4,5,7]，target = 13.
首先 nums[i] = 1; 那么二和问题要寻找的两数之和应该小于12。nums[j] 从索引 i 后面的元素3开始，nums[k]从末端的7开始。nums[j] + nums[k] 小于12。这样的数有几对呢？

我们可以知道，如果nums[j]不变，有[3,4],[3,5],[3,7]这三对，即（k - j）对。此时我们累加这个数值，将i加一。这时有[4,5],[4,7]这两对。按照这样的算法，一共得到有六对满足条件的数。

代码

public class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        int result = 0;
        Arrays.sort(nums);
        for(int i = 0; i <= nums.length-3; i++) {
            int lo = i+1;
            int hi = nums.length-1;
            while(lo < hi) {
                if(nums[i] + nums[lo] + nums[hi] < target) {
                    result += hi - lo;
                    lo++;
                } else {
                    hi--;
                }
            }
        }
        return result;
    }
}

复杂度分析

• 时间复杂度
  • O(n^2)
• 空间复杂度
  • O(1)

解法二 Binary Search

思路

代码

复杂度分析

• 时间复杂度
  • 最好情况
  • 最坏情况
  • 平均情况
• 空间复杂度

Takeaway

本作品采用《CC 协议》，转载必须注明作者和本文链接