259. 3Sum Smaller

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

Given an array of n integers nums and an integer 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.

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

Example 1:

Input: nums = [-2,0,1,3], target = 2
Output: 2
Explanation: Because there are two triplets which sums are less than 2:
[-2,0,1]
[-2,0,3]

Example 2:

Input: nums = [], target = 0
Output: 0

Example 3:

Input: nums = [0], target = 0
Output: 0

Code

class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        int res = 0;
        Arrays.sort(nums);

        for(int i = 0; i < nums.length; i++){
            int left = i + 1;
            int right = nums.length - 1;
            while(left < right){
                if(nums[i] + nums[left] + nums[right] < target){
                    // 因为已经是排序过的，所以如果nums[left] + nums[right]的值都小于target
                    // 那nums[left] + nums[right - 1]也一定小于target
                    // 所以可以让res直接加上这段index的差值
                    // 0，1，2，3，4，5
                    //    l         r
                    // 结果就是r - l = 4
                    // 对应[1,5],[1,4],[1,3],[1,2]这四个结果
                    res += right - left;
                    left++;
                } else {
                    right--;
                }
            }
        }

        return res;
    }
}

class Solution:
    def threeSumSmaller(self, nums: List[int], target: int) -> int:
        if not nums or len(nums) < 3:
            return 0

        nums.sort()

        res = 0
        for i in range(0, len(nums) - 2, 1):
            num1 = nums[i]
            left = i + 1
            right = len(nums) - 1

            while left < right:
                sum = num1 + nums[left] + nums[right]
                if sum < target:
                    res += right - left
                    left += 1
                else:
                    right -= 1

        return res