3Sum Smaller

Salamander 发布于2019-08-14 17:19 / 3360人阅读

摘要：题目链接，从小到大排序固定第一个数字，从后面的数字里选第二个第三个后两个数字，用来找，从开始因为所有之间的数和组合都

3Sum Smaller

题目链接：https://leetcode.com/problems...

sort，从小到大排序

固定第一个数字index = i，从后面的数字里选第二个第三个

后两个数字，用2 points来找，从j = i + 1, k = len() - 1开始：

if n[j] + n[k] < target - n[i]: count += (k-i), j++
因为所有(j+1, k)之间的数和n[j]组合都< target - n[i]

if n[j] + n[k] >= target - n[i]: k--

public class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        if(nums == null || nums.length < 3) return 0;
        // sort first
        Arrays.sort(nums);
        /* enumerate 1st num: k
         * 2 points find 2nd, 3rd
         * initial: i = k + 1, j = len(nums) - 1
         * case 1: n[i] + n[j] < target - n[k]: count += j - i, i++
         * case 2: > : j--
         */
        int count = 0;
        for(int k = 0; k < nums.length - 2; k++) {
            int i = k + 1, j = nums.length - 1;
            while(i < j) {
                if(nums[i] + nums[j] >= target - nums[k]) j--;
                else {
                    count += j - i;  i++;
                }
            }
        }
        return count;
    }
}

云服务器 GPU云服务器 Smaller

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

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

[Leetcode] 3Sum Smaller 三数较小和

摘要：排序法复杂度时间空间思路解题思路和一样，也是先对整个数组排序，然后一个外层循环确定第一个数，然后里面使用头尾指针和进行夹逼，得到三个数的和。 3Sum Smaller Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 = target){ ...

tomato 2019-08-14 12:35 评论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
[Leetcode] 3Sum 4Sum 3Sum Closet 多数和

摘要：为了避免得到重复结果，我们不仅要跳过重复元素，而且要保证找的范围要是在我们最先选定的那个数之后的。而计算则同样是先选一个数，然后再剩下的数中计算。 2Sum 在分析多数和之前，请先看Two Sum的详解 3Sum 请参阅：https://yanjia.me/zh/2019/01/... 双指针法复杂度时间 O(N^2) 空间 O(1) 思路 3Sum其实可以转化成一个2Sum的题，...

trigkit4 2019-08-14 12:29 评论0 收藏0
[Leetcode] Two Sum, 3Sum,4Sum,4SumII,3Sum Closet

摘要：解题思路题目要求两个数和等于，返回其题目说明不会有重复情况，所以我们一旦发现符合情况的，就可以直接结束循环并返回。特殊情况就是正好等于，那肯定是最接近的情况，直接返回即可。 Two SumGiven an array of integers, return indices of the two numbers such that they add up to a specific ta...

EddieChan 2019-08-19 10:45 评论0 收藏0
【LC总结】K Sum (Two Sum I II/3Sum/4Sum/3Sum Closest)

摘要：找符合条件的总数。双指针区间考虑边界，长度，为空，等。之后的范围用双指针和表示。若三个指针的数字之和为，加入结果数组。不要求，所以不用判断了。同理，头部两个指针向后推移，后面建立左右指针夹逼，找到四指针和为目标值的元素。 Two Sum Problem Given an array of integers, find two numbers such that they add up ...

awesome23 2019-08-14 15:50 评论0 收藏0