女人床叫声视频,11届全运会开幕式,福州一中网校
题目:
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?
方法一:
class solution { public: int threesumsmaller(vector<int>& nums, int target) { int res = 0; sort(nums.begin(), nums.end()); for (int i = 0; i < int(nums.size() - 2); ++i) { int left = i + 1, right = nums.size() - 1, sum = target - nums[i]; for (int j = left; j <= right; ++j) { for (int k = j + 1; k <= right; ++k) { if (nums[j] + nums[k] < sum) ++res; } } } return res; } };
方法二:
class solution2 { public: int threesumsmaller(vector<int>& nums, int target) { if (nums.size() < 3) return 0; int res = 0, n = nums.size(); sort(nums.begin(), nums.end()); for (int i = 0; i < n - 2; ++i) { int left = i + 1, right = n - 1; while (left < right) { if (nums[i] + nums[left] + nums[right] < target) { res += right - left; ++left; } else { --right; } } } return res; } };
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论