1 题目
题目：两数之和-不同组成（Two Sum - Unique pairs）
描述：给一整数数组, 找到数组中有多少组 不同的元素对 有相同的和, 且和为给出的 target 值, 返回对数.
lintcode题号——587，难度——medium
样例1：
输入: nums = [1,1,2,45,46,46], target = 47
输出: 2
解释:
1 + 46 = 47
2 + 45 = 47
样例2：
输入: nums = [1,1], target = 2
输出: 1
解释:
1 + 1 = 2
2 解决方案
2.1 思路
??先对数组排序，然后两个指针分别从头尾开始向中间走，若指针指向的两个值的和小于目标值，则左指针往右一步，若大于目标值，则右指针往左一步，直到找到结果。原数组中可能存在重复的元素，
2.2 时间复杂度
??时间复杂度为O(n)。
2.3 空间复杂度
??空间复杂度为O(1)。
3 源码
细节：
- 使用对向双指针的方式。
- 需要去除重复，方式是在找到结果对之后，左边和右边指针都跳过与当前位置重复的数。
- 若直接对原数组去重，则需要单独处理类似24 + 24 = 48这类两数相同且和为target的情况。
C++版本：
/**
* @param nums: an array of integer
* @param target: An integer
* @return: An integer
*/
int twoSum6(vector<int> &nums, int target) {
// write your code here
int result = 0;
if (nums.empty())
{
return result;
}
// 对数组先排序
sort(nums.begin(), nums.end());
int left = 0;
int right = nums.size() - 1;
while (left < right)
{
if (nums.at(left) + nums.at(right) < target)
{
left++;
}
else if (nums.at(left) + nums.at(right) > target)
{
right--;
}
else
{
left++;
right--;
result++; // 找到配对，结果+1
while (left < right && nums.at(left) == nums.at(left - 1)) // 左边跳过相同的数
{
left++;
}
while (left < right && nums.at(right) == nums.at(right + 1)) // 右边跳过相同的数
{
right--;
}
}
}
return result;
}
