代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
Given an array of n
integers nums
and an integer 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
.
Follow up: Could you solve it in O(n2)
runtime?
Example 1:
Input: nums = [-2,0,1,3], target = 2 Output: 2 Explanation: Because there are two triplets which sums are less than 2: [-2,0,1] [-2,0,3]
Example 2:
Input: nums = [], target = 0 Output: 0
Example 3:
Input: nums = [0], target = 0 Output: 0
Constraints:
n == nums.length
0 <= n <= 300
-100 <= nums[i] <= 100
-100 <= target <= 100
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;
};
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。