16. 最接近的三数之和
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例：
输入：nums = [-1,2,1,-4], target = 1 输出：2 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
题目分析:
排序和双指针
AC代码
#include<bits/stdc++.h> using namespace std; //排序和双指针 int threeSumClosest(vector<int>& nums, int target) { sort(nums.begin(),nums.end()); int ans = nums[0]+nums[1]+nums[2];//存放答案 int L,R,len = nums.size(),temp; for(int i = 0;i < len;i++){ L = i+1; R = len-1; while(L<R){ temp = nums[i]+nums[L]+nums[R]; if(abs(temp-target)<abs(ans-target)){ ans = temp; } if(temp>target){ R--; }else if(temp < target){ L++; }else{ return temp; } } } return ans; } int main() { vector<int> nums = {-1,2,1,-4}; int target = 1+; cout<<threeSumClosest(nums,target)<<endl; return 0; }
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]]
思路分析:
双指针+排序
使用四个指针a,b,c,d.先固定a,b在左边,c=b+1,d = len-1; 移动两个指针包夹求解. 求得nums[a]+nums[b]+nums[c]+nums[d]==target的解.偏大时d左移,偏小时c右移.c和d相遇时,表示当前以a,b为最小值的解已经完全求得.b++,进入下一轮循环,当b循环结束后a++.进入下一轮a循环.
时间复杂度:O(N^3)
参考代码
#include<bits/stdc++.h> using namespace std; //https://leetcode-cn.com/problems/4sum/submissions/ //https://leetcode-cn.com/problems/4sum/solution/shuang-zhi-zhen-jie-fa-can-zhao-san-shu-zhi-he-ge-/ vector<vector<int>> fourSum(vector<int>& nums, int target) { sort(nums.begin(),nums.end()); vector<vector<int>> ans; int len = nums.size(); long long a,b,c,d,temp; for( a = 0; a<= len - 4; a++) { //外层对应a if(a>0&&nums[a]==nums[a-1]) { //对a去重 continue; } for( b = a+1; b<len; b++) { //从这里开始相当于重新回到了三数之和. c = b+1; d = len - 1; if(b>a+1&&nums[b]==nums[b-1]) { continue; } while(c<d) { temp = 0; temp += nums[a]; temp += nums[b]; temp += nums[c]; temp += nums[d]; //long long temp = nums[a]+nums[b]+nums[c]+nums[d]; 这样计算会溢出.. if( temp> target) { d--; } else if(temp < target) { c++; } else if(temp == target) { ans.push_back({nums[a],nums[b],nums[c],nums[d]}); while(c+1 < d && nums[c]==nums[c+1]) { //c去重 c++; } while(d-1>c && nums[d-1]==nums[d]) { //d去重 d--; } d--; c++; } } } } return ans; } int main() { vector<int> nums = {1000000000,1000000000,1000000000,1000000000}; int target = 0; cout<<fourSum(nums, target).size()<<endl; return 0; }
