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?

给一个整数数组nums和一个target，找出所有3个指针对应数字和小于target的组合的数量。

解法1: 暴力brute force, 找出所有组合的和，然后找出小于target的组合，O(n^3)

解法2: 双指针，类似3Sum的方法，但由于只需要求count，而不用求出每个组合，可以做到O(n^2)。还是先对数组排序，然后用2个指针前后夹逼，当i, lo, hi这个组合满足条件时，在[lo, hi]这个闭合区间内的所有组合也应该满足条件，所以可以直接count += hi - lo，然后lo++，增大三个值的和来继续尝试，假如不满足条件，则hi--来缩小三个值的和。

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:

# 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++:

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 题目汇总

巴特西

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

All LeetCode Questions List 题目汇总

最新文章

热门文章