郑州网站建设服务,优化营商环境个人心得,html做静态网站,网站开发流程怎么写#x1f604;#x1f60a;#x1f606;#x1f603;#x1f604;#x1f60a;#x1f606;#x1f603;
开始cpp刷题之旅。
目标#xff1a;执行用时击败90%以上使用 C 的用户。 18. 四数之和
给你一个由 n 个整数组成的数组 nums #xff0c;和一个目标值 target…
开始cpp刷题之旅。
目标执行用时击败90%以上使用 C 的用户。 18. 四数之和
给你一个由 n 个整数组成的数组 nums 和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] 若两个四元组元素一一对应则认为两个四元组重复
0 a, b, c, d n a、b、c 和 d 互不相同 nums[a] nums[b] nums[c] nums[d] target 你可以按 任意顺序 返回答案 。
示例 1
输入nums [1,0,-1,0,-2,2], target 0 输出[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]] 示例 2
输入nums [2,2,2,2,2], target 8 输出[[2,2,2,2]]
解题
这道题解法类似于三数之和不过三数之和是一个for循环加双指针而本道题可以使用双重for循环加上双指针这样就正好是四数之和了。
思路大致相同首先是进行排序从小到大。
接着中间需要加一些判断比如重复的只取第一个值即可。
第一层循环和第二层循环中当最大的四个数都小于target时都是不需要再进行考虑了使用continue即可。
第一层和第二层中当最小的四个数仍大于target时由于是从小到大排序所以后面肯定是没有值了此时可以直接break。
其它的也没啥了感觉和三数之和几乎一样的思路不做过多解释了。
本题代码虽然比较多毕竟是多了一层遍历和条件判断。
但是它的思路很简单应该都能看懂。
class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {vectorvectorint quadruplets;if (nums.size() 4) {return quadruplets;}sort(nums.begin(), nums.end());int length nums.size();for (int i 0; i length - 3; i) {if (i 0 nums[i] nums[i - 1]) {continue;}if ((long) nums[i] nums[i 1] nums[i 2] nums[i 3] target) {break;}if ((long) nums[i] nums[length - 3] nums[length - 2] nums[length - 1] target) {continue;}for (int j i 1; j length - 2; j) {if (j i 1 nums[j] nums[j - 1]) {continue;}if ((long) nums[i] nums[j] nums[j 1] nums[j 2] target) {break;}if ((long) nums[i] nums[j] nums[length - 2] nums[length - 1] target) {continue;}int left j 1, right length - 1;while (left right) {long sum (long) nums[i] nums[j] nums[left] nums[right];if (sum target) {quadruplets.push_back({nums[i], nums[j], nums[left], nums[right]});while (left right nums[left] nums[left 1]) {left;}left;while (left right nums[right] nums[right - 1]) {right--;}right--;} else if (sum target) {left;} else {right--;}}}}return quadruplets;}
};提交记录
