摘要:题目链接,从小到大排序固定第一个数字,从后面的数字里选第二个第三个后两个数字,用来找,从开始因为所有之间的数和组合都
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; } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/66566.html
摘要:排序法复杂度时间空间思路解题思路和一样,也是先对整个数组排序,然后一个外层循环确定第一个数,然后里面使用头尾指针和进行夹逼,得到三个数的和。 3Sum Smaller Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 = target){ ...
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++) { ...
摘要:为了避免得到重复结果,我们不仅要跳过重复元素,而且要保证找的范围要是在我们最先选定的那个数之后的。而计算则同样是先选一个数,然后再剩下的数中计算。 2Sum 在分析多数和之前,请先看Two Sum的详解 3Sum 请参阅:https://yanjia.me/zh/2019/01/... 双指针法 复杂度 时间 O(N^2) 空间 O(1) 思路 3Sum其实可以转化成一个2Sum的题,...
摘要:解题思路题目要求两个数和等于,返回其题目说明不会有重复情况,所以我们一旦发现符合情况的,就可以直接结束循环并返回。特殊情况就是正好等于,那肯定是最接近的情况,直接返回即可。 Two SumGiven an array of integers, return indices of the two numbers such that they add up to a specific ta...
摘要:找符合条件的总数。双指针区间考虑边界,长度,为空,等。之后的范围用双指针和表示。若三个指针的数字之和为,加入结果数组。不要求,所以不用判断了。同理,头部两个指针向后推移,后面建立左右指针夹逼,找到四指针和为目标值的元素。 Two Sum Problem Given an array of integers, find two numbers such that they add up ...
阅读 2831·2023-04-26 02:23
阅读 1570·2021-11-11 16:55
阅读 3149·2021-10-19 11:47
阅读 3352·2021-09-22 15:15
阅读 1975·2019-08-30 15:55
阅读 1033·2019-08-29 15:43
阅读 1288·2019-08-29 13:16
阅读 2188·2019-08-29 12:38