[LeetCode] 259. 3Sum Smaller 三数之和较小值

2021年09月15日 阅读数:3
这篇文章主要向大家介绍[LeetCode] 259. 3Sum 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.html

For example, given nums = [-2, 0, 1, 3], and target = 2.java

Return 2. Because there are two triplets which sums are less than 2:python

[-2, 0, 1]
[-2, 0, 3]

Follow up:
Could you solve it in O(n2) runtime?数组

给一个整数数组nums和一个target,找出全部3个指针对应数字和小于target的组合的数量。less

解法1: 暴力brute force, 找出全部组合的和,而后找出小于target的组合,O(n^3)post

解法2: 双指针,相似3Sum的方法,但因为只须要求count,而不用求出每一个组合,能够作到O(n^2)。仍是先对数组排序,而后用2个指针先后夹逼,当i, lo, hi这个组合知足条件时,在[lo, hi]这个闭合区间内的全部组合也应该知足条件,因此能够直接count += hi - lo,而后lo++,增大三个值的和来继续尝试,假如不知足条件,则hi--来缩小三个值的和。url

Java:指针

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

Python:code

# Time:  O(n^2)
# Space: O(1)
class Solution:
    # @param {integer[]} nums
    # @param {integer} target
    # @return {integer}
    def threeSumSmaller(self, nums, target):
        nums.sort()
        n = len(nums)

        count, k = 0, 2
        while k < n:
            i, j = 0, k - 1
            while i < j:  # Two Pointers, linear time.
                if nums[i] + nums[j] + nums[k] >= target:
                    j -= 1
                else:
                    count += j - i
                    i += 1
            k += 1

        return count  

C++:htm

class Solution {
public:
    int threeSumSmaller(vector<int>& nums, int target) {
        if (nums.size() < 3) return 0;
        int res = 0, n = nums.size();
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n - 2; ++i) {
            int left = i + 1, right = n - 1;
            while (left < right) {
                if (nums[i] + nums[left] + nums[right] < target) {
                    res += right - left;
                    ++left;
                } else {
                    --right;
                }
            }
        }
        return res;
    }
};

 

 

相似题目:

[LeetCode] 15. 3Sum 三数之和

[LeetCode] 16. 3Sum Closest 最近三数之和

 

All LeetCode Questions List 题目汇总