classSolution { public: vector<vector<int>> threeSum(vector<int>& nums) { sort(nums.begin(), nums.end()); int n = nums.size(); vector<vector<int>> ans; for (int i = 0; i < n - 2; i ++) { int x = nums[i]; if (i > 0 && x == nums[i - 1]) continue; if (x + nums[i + 1] + nums[i + 2] > 0) break; if (x + nums[n - 1] + nums[n - 2] < 0) continue; int left = i + 1; int right = n - 1; while (left < right) { if (x + nums[left] + nums[right] < 0) { left ++; } elseif (x + nums[left] + nums[right] > 0) { right --; } else { ans.push_back({x, nums[left], nums[right]}); left ++; while (left < right && nums[left] == nums[left - 1]) left ++; right --; while (left < right && nums[right] == nums[right + 1]) right --; } } } return ans; } };
leetcode 2824
给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 target ,请你返回满足 0 <= i < j < n 且 nums[i] + nums[j] < target 的下标对 (i, j) 的数目。
classSolution { public: intcountPairs(vector<int>& nums, int target){ int ans = 0; sort(nums.begin(), nums.end()); int n = nums.size(); int left = 0, right = n - 1;
while (left < right) { if (nums[left] + nums[right] >= target) { right --; } else { ans += right - left; left ++; } } return ans; } };
classSolution { public: intthreeSumClosest(vector<int>& nums, int target){ sort(nums.begin(), nums.end()); int n = nums.size(); int diff = INT_MAX; int ans = 0; for (int i = 0; i < n - 2; i ++) { int x = nums[i]; int left = i + 1, right = n - 1; int s = x + nums[i + 1] + nums[i + 2]; if (s > target) { if (s - target < diff) { ans = s; } break; } s = x + nums[n - 1] + nums[n - 2]; if (s < target) { if (target - s < diff) { diff = target - s; ans = s; } continue; } while (left < right) { if (abs(target - (x + nums[left] + nums[right])) < diff) { ans = x + nums[left] + nums[right]; diff = abs(target - (x + nums[left] + nums[right])); } if (x + nums[left] + nums[right] < target) { left ++; } elseif (x + nums[left] + nums[right] > target) { right --; } elsebreak; }
classSolution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { int n = nums.size(); vector<vector<int>> ans; sort(nums.begin(), nums.end()); for (int i = 0; i < n - 3; i ++) { if (i > 0 && nums[i] == nums[i - 1]) continue; for (int j = i + 1; j < n - 2; j ++) { if (j > i + 1 && nums[j] == nums[j - 1]) continue; long s = (long)nums[i] + nums[j] + nums[j + 1] + nums[j + 2]; if (s > target) break; s = (long)nums[i] + nums[j] + nums[n - 1] + nums[n - 2]; if (s < target) continue;
int left = j + 1, right = n - 1;
while (left < right) { long s = (long)nums[i] + nums[j] + nums[left] + nums[right]; if (s < target) { left ++; } elseif (s > target) { right --; } else { ans.push_back({nums[i], nums[j], nums[left], nums[right]}); left ++; while (left < right && nums[left] == nums[left - 1]) left++; right --; while (left < right && nums[right] == nums[right + 1]) right --; } } } } return ans; } };
leetcode 611
给定一个包含非负整数的数组 nums ,返回其中可以组成三角形三条边的三元组个数。
组成三角形,换句话说,也就是对三条边的任意两条边相加,其值都大于第三条边。
排序后,随机选出3个值,a < b < c。显然,a + c > b, b + c > a, 我们需要确定是否 a + b > c。这就很像leetcode 2824这题。此时,是 > target的。所以,我们是要固定右端点。
int ans = 0; int n = nums.size(); for (int i = n - 1; i >= 2; i --) { int left = 0, right = i - 1; if (nums[i - 1] + nums[i - 2] < nums[i]) continue; while (left < right) { if (nums[left] + nums[right] <= nums[i]) { left ++; } else { ans += right - left; right --; } } } return ans; } };