代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
给定一个长度为 n 的整数数组和一个目标值 target,寻找能够使条件 nums[i] + nums[j] + nums[k] < target
成立的三元组 i, j, k
个数(0 <= i < j < k < n
)。
示例:
[-2,0,1,3]
进阶:是否能在 O(n2) 的时间复杂度内解决?
双指针解决。
class Solution:
def threeSumSmaller(self, nums: List[int], target: int) -> int:
def threeSumSmaller(nums, start, end, target):
count = 0
while start < end:
if nums[start] + nums[end] < target:
count += (end - start)
start += 1
else:
end -= 1
return count
nums.sort()
n, count = len(nums), 0
for i in range(n - 2):
count += threeSumSmaller(nums, i + 1, n - 1, target - nums[i])
return count
class Solution {
public int threeSumSmaller(int[] nums, int target) {
Arrays.sort(nums);
int n = nums.length;
int count = 0;
for (int i = 0; i < n - 2; ++i) {
count += threeSumSmaller(nums, i + 1, n - 1, target - nums[i]);
}
return count;
}
private int threeSumSmaller(int[] nums, int start, int end, int target) {
int count = 0;
while (start < end) {
if (nums[start] + nums[end] < target) {
count += (end - start);
++start;
} else {
--end;
}
}
return count;
}
}
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var threeSumSmaller = function (nums, target) {
let len = nums.length;
if (len < 3) return 0;
nums.sort((a, b) => a - b)
let res = 0;
for (let i = 0; i < len - 2; i++) {
let left = i + 1, right = len - 1;
if (nums[i] + nums[left] + nums[i + 2] >= target) break;
while (left < right) {
if (nums[i] + nums[left] + nums[right] < target) {
res += (right - left);
left++;
continue;
} else {
right--;
continue;
}
}
}
return res;
};
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。