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 协议》,转载必须注明作者和本文链接
讨论数量: 1

思路不应该是找出最小的三个数 就可以吗 循环一遍就可以。 不需要排序这么复杂吧。

4年前 评论
Borris (楼主) 4年前
swing07 (作者) 4年前

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