[Leetcode] 3Sum Smaller 三数较小和

tomato 发布于2019-08-14 12:35 / 328人阅读

摘要：排序法复杂度时间空间思路解题思路和一样，也是先对整个数组排序，然后一个外层循环确定第一个数，然后里面使用头尾指针和进行夹逼，得到三个数的和。

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.
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?

排序法 复杂度

时间 O(N^2) 空间 O(1)

思路

解题思路和3SUM一样，也是先对整个数组排序，然后一个外层循环确定第一个数，然后里面使用头尾指针left和right进行夹逼，得到三个数的和。如果这个和大于或者等于目标数，说明我们选的三个数有点大了，就把尾指针right向前一位（因为是排序的数组，所以向前肯定会变小）。如果这个和小于目标数，那就有right - left个有效的结果。为什么呢？因为假设我们此时固定好外层的那个数，还有头指针left指向的数不变，那把尾指针向左移0位一直到左移到left之前一位，这些组合都是小于目标数的。

代码

public class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        // 先将数组排序 
        Arrays.sort(nums);
        int cnt = 0;
        for(int i = 0; i < nums.length - 2; i++){
            int left = i + 1, right = nums.length - 1;
            while(left < right){
                int sum = nums[i] + nums[left] + nums[right];
                // 如果三个数的和大于等于目标数，那将尾指针向左移
                if(sum >= target){
                    right--;
                // 如果三个数的和小于目标数，那将头指针向右移
                } else {
                    // right - left个组合都是小于目标数的
                    cnt += right - left;
                    left++;
                }
            }
        }
        return cnt;
    }
}

云服务器 GPU云服务器 Smaller LeetCode LeetCode_String leetcode_35_SearchIn

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64579.html

LeetCode 之 JavaScript 解答第十五题 —— 三数之和（3Sum）

摘要：如果三个数据相加等于了，就存储该三个值且更新和指针。边界条件判断数组内元素是否都为整数或负数，直接返回。判断和指针的大小关系。在原来数组上进行排序，不生成副本。 Time：2019/4/3Title:3SumDifficulty: mediumAuthor:小鹿题目三：ADD Two Numbers Given an array nums of n integers, are the...

Wildcard 2019-08-23 16:45 评论0 收藏0
[LintCode/LeetCode] 3Sum

摘要：双指针法的解法。然后用和夹逼找到使三数和为零的三数数列，放入结果数组。对于这三个数，如果循环的下一个数值和当前数值相等，就跳过以避免中有相同的解。 Problem Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplet...

Sunxb 2019-08-14 15:42 评论0 收藏0
3Sum Smaller

摘要：题目链接，从小到大排序固定第一个数字，从后面的数字里选第二个第三个后两个数字，用来找，从开始因为所有之间的数和组合都 3Sum Smaller 题目链接：https://leetcode.com/problems... sort，从小到大排序固定第一个数字index = i，从后面的数字里选第二个第三个后两个数字，用2 points来找，从j = i + 1, k = len(...

Salamander 2019-08-14 17:19 评论0 收藏0
思维导图整理大厂面试高频数组补充1: 最接近的三数之和和三数之和的两个不同之处, 力扣16

摘要：此专栏文章是对力扣上算法题目各种方法的总结和归纳整理出最重要的思路和知识重点并以思维导图形式呈现当然也会加上我对导图的详解目的是为了更方便快捷的记忆和回忆算法重点不用每次都重复看题解毕竟算法不是做了一遍就能完全记住的所 ...

longmon 2021-11-12 10:36 评论0 收藏0
[LintCode] 3Sum Smaller

Problem Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 = target) return 0; int count = 0; for (int i = 0; i < nums.length-2; i++) { ...

AprilJ 2019-08-15 18:09 评论0 收藏0