两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
思路
暴力求解
代码
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> index;
for(int i = 0;i<nums.size();i++)
{
int j=i+1;
while(j<nums.size())
{
if(nums[i]+nums[j]==target)
{
index.push_back(i);
index.push_back(j);
return index;
}
j++;
}
}
return {-1,-1};
}
};
三数之和
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
参考代码
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int target;
vector<vector<int>> ans;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
if ((target = nums[i]) > 0) break;
int l = i + 1, r = nums.size() - 1;
while (l < r) {
if (nums[l] + nums[r] + target < 0) ++l;
else if (nums[l] + nums[r] + target > 0) --r;
else {
ans.push_back({target, nums[l], nums[r]});
++l, --r;
while (l < r && nums[l] == nums[l - 1]) ++l;
while (l < r && nums[r] == nums[r + 1]) --r;
}
}
}
return ans;
}
};
代码
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
//思路是三指针，第一步排序，之后先固定左指针，若三指针之和>0，则左移右指针;若<0则右移中指针;若和为0，则记录下来Index,并将中指针右移和右指针左移。
vector<vector<int> >res;
//1、排序
sort(nums.begin(),nums.end());
// int i1=0;
// while(i1<nums.size())
for(int i1=0;i1<nums.size();i1++)
{
if(i1>0&&nums[i1]==nums[i1-1]) continue;
if(nums[i1]>0) break;
int i2=i1+1;
int i3=nums.size()-1;
while(i2<i3)
{
if(nums[i1]+nums[i2]+nums[i3]==0)
{
res.push_back({nums[i1],nums[i2],nums[i3]});
i3--;
while(i2<i3&&nums[i3]==nums[i3+1])
{
i3--;
}
i2++;
while(i2<i3&&nums[i2]==nums[i2-1])
{
i2++;
}
}
else if(nums[i1]+nums[i2]+nums[i3]<0)
{
i2++;
}
else
{
i3--;
}
}
}
return res;
}
// vector<vector<int>> threeSum(vector<int>& nums) {
// //思路是三指针，第一步排序，之后先固定左指针，若三指针之和>0，则左移右指针;若<0则右移中指针;若和为0，则记录下来Index,并将中指针右移和右指针左移。
// vector<vector<int> >res;
// //1、排序
// sort(nums.begin(),nums.end());
// if(nums[0]>0) return res;
// int i3=nums.size()-1;
// int i1=0;
// while(i1<nums.size()-1)
// {
// if(i1>0&&nums[i1]==nums[i1-1]) {i1++;continue;}
// int i2=i1+1;
// while(i2<i3)
// {
// if(nums[i1]+nums[i2]+nums[i3]==0)
// {
// res.push_back({nums[i1],nums[i2],nums[i3]});
// i3--;
// while(i2<i3&&nums[i3]==nums[i3+1])
// {
// i3--;
// }
// i2++;
// while(i2<i3&&nums[i2]==nums[i2-1])
// {
// i2++;
// }
// }
// else if(nums[i1]+nums[i2]+nums[i3]<0)
// {
// i2++;
// }
// else
// {
// i3--;
// }
// }
// i1++;
// }
// return res;
// }
};
注：注释掉的不知道为什么不能ac。。。
