LeetCode 259. 3Sum Smaller 三数之和比target小的triplet有多少

冷不防 2021-09-25 00:58 152阅读 0赞

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*(*n^*2) runtime?

import java.util.Arrays;
    
    /**
     * @Author you guess
     * @Date 2020/12/15 21:46
     * @Version 1.0
     * @Desc
     */
    public class LeetCode_259_3SumSmaller {
    
        public int threeSumSmaller(int[] nums, int target) {
            Arrays.sort(nums);
            int low, high, sum;
            int count = 0;
            for (int i = 0; i < nums.length - 2; i++) {//只能遍历到最后三位，所以前面的只能到nums[len-3]
                low = i + 1;
                high = nums.length - 1;
                while (low < high) {
                    sum = nums[i] + nums[low] + nums[high];
                    if (sum < target) {
                        count += high - low;
                        low++;
                    } else if (sum >= target) {
                        high--;
                    }
                }
            }
            return count;
        }
    
        public static void main(String[] args) {
            LeetCode_259_3SumSmaller main = new LeetCode_259_3SumSmaller();
            System.out.println(main.threeSumSmaller(new int[]{-2, 0, 1, 3}, 5));//4
            System.out.println(main.threeSumSmaller(new int[]{-2, 0, 1, 3}, 2));//2
        }
    
    }

T(n) = O(n^2)

发表评论取消回复

表情：

评论列表（有 0 条评论，152人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode 15 :三数之和（3Sum）

英文题目 Given an array nums of n integers, are there elements a, b, c in nums such that

╰+攻爆jí腚メ/ 2023年07月17日 04:36/ 0 赞/ 99 阅读

相关 LeetCode：15. 3Sum 三数之和（C语言）

题目描述：给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组

小鱼儿/ 2023年07月08日 11:28/ 0 赞/ 76 阅读

相关 leetcode259. 较小的三数之和

给定一个长度为 n 的整数数组和一个目标值 target，寻找能够使条件 nums\[i\] + nums\[j\] + nums\[k\] < target 成立的三元组 i

喜欢ヅ旅行/ 2023年07月03日 10:43/ 0 赞/ 64 阅读

相关 15. 3Sum(三数之和——）

我还以为我写了blog3sum，结果没找都。那就再复习一遍给定阵列nums的Ñ整数，在那里元件a，b，c 在nums使得a + b + c = 0 在给出零总和的数组中找

た入场券/ 2022年12月02日 11:00/ 0 赞/ 205 阅读

相关算法：三数之和（3sum）。

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。注意：

ゞ浴缸里的玫瑰/ 2022年11月27日 01:56/ 0 赞/ 216 阅读

相关 [LeetCode]15. 3Sum三数之和

Given an array `nums` of n integers, are there elements a, b, c in `nums` such that a \+

超、凢脫俗/ 2022年10月02日 14:57/ 0 赞/ 236 阅读

相关 LeetCode 15. 3Sum (三数之和)

题目描述：给定一个包含 n 个整数的数组 `nums`，判断 `nums` 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的

超、凢脫俗/ 2022年05月11日 00:20/ 0 赞/ 245 阅读

相关【leetcode】三数之和（3Sum）【python】AC解答

题目链接：[三数之和][Link 1] ![在这里插入图片描述][70] 利用和为0的性质，可以不用O(N^3) 而使用O(N^2)来解决 class S

淡淡的烟草味﹌/ 2022年05月08日 02:40/ 0 赞/ 208 阅读

相关 leetcode第15题 3Sum(三数之和)

比较简单的一道题，题目的大意是说： > 给定一个长度为n的整数数组nums，从数组中找出所有不重复的（三个数相加等于0的组合）。 > 注意，仅字典序不同的、包含数字相同

我会带着你远行/ 2022年03月08日 05:08/ 0 赞/ 281 阅读

相关 LeetCode 259. 3Sum Smaller 三数之和比target小的triplet有多少

Given an array of n integers nums and a target, find the number of index triplets `i, j,

冷不防/ 2021年09月25日 00:58/ 0 赞/ 153 阅读