一、题目

在这里插入图片描述

二、双指针法

思路分析：我们使用双指针法，但这道题因为要求数组三个元素的和，一共用到了三个指针，但在循环当中只有两个指针起作用，还是把解法称为双指针法。题目要求不能有重复的三元组，那么我们在程序中判断第i个元素是否和i-1哥元素相同，如果相同则跳过第i元素。while 语句当中，判断 nums[left] 和 nums[right] 的和是否大于target，即判断三元素和是否大于0，当跳出循环时，和必然小于等于0，进行判断，如果等于0添加进结果中，否则继续循环。
程序如下：

class Solution {
public:// 双指针法vector<vector<int>> threeSum(vector<int>& nums) {int n = nums.size();sort(nums.begin(), nums.end());	// 升序排列vector<vector<int>> result;if (nums[0] > 0) return result;	// 最小值都大于零，不存在三元组和为0for (int i = 0; i < n; ++i) {if (i > 0 && nums[i] == nums[i - 1]) continue;	// i去重int right = n - 1;		// 最右端int target = -nums[i];	for (int left = i + 1; left < n; ++left) {if (left > i + 1 && nums[left] == nums[left - 1]) continue;	// left去重while (left < right && nums[left] + nums[right] > target) {--right;		// 三者之和大于0，right收缩，一直收缩到小于等于0或者left=right为止}if (left == right)	break;	// 不存在三元组，因此break。if (nums[left] + nums[right] == target) {result.push_back({ nums[i], nums[left], nums[right] });//result.push_back({ i, left, right });	// 调试用}}}return result;}
};

复杂度分析：

时间复杂度： $O(n^2)$ 。
空间复杂度： $O (1)$ 。

三、完整代码

# include <iostream>
# include <string>
# include <vector>
# include <algorithm>
using namespace std;void GeneratorVector(int arr[], int arr_len, vector<int>& v) {for (int i = 0; i < arr_len; i++) {v.push_back(arr[i]);}
}void my_print1(vector<int>& v, string str) {cout << str << endl;for (vector<int>::iterator it = v.begin(); it < v.end(); ++it) {cout << *it << ' ';}cout << endl;
}void my_print2(vector<vector<int>>& v, string str) {cout << str << endl;for (vector<vector<int>>::iterator vit = v.begin(); vit < v.end(); ++vit) {for (vector<int>::iterator it = (*vit).begin(); it < (*vit).end(); ++it) {cout << *it << ' ';}cout << endl;}
}class Solution {
public:// 双指针法vector<vector<int>> threeSum(vector<int>& nums) {int n = nums.size();sort(nums.begin(), nums.end());	// 升序排列vector<vector<int>> result;if (nums[0] > 0) return result;	// 最小值都大于零，不存在三元组和为0for (int i = 0; i < n; ++i) {if (i > 0 && nums[i] == nums[i - 1]) continue;	// i去重int right = n - 1;		// 最右端int target = -nums[i];	for (int left = i + 1; left < n; ++left) {if (left > i + 1 && nums[left] == nums[left - 1]) continue;	// left去重while (left < right && nums[left] + nums[right] > target) {--right;		// 三者之和大于0，right收缩，一直收缩到小于等于0或者left=right为止}if (left == right)	break;	// 不存在三元组，因此break。if (nums[left] + nums[right] == target) {result.push_back({ nums[i], nums[left], nums[right] });//result.push_back({ i, left, right });	// 调试用}}}return result;}
};int main()
{int arr[] = {-1, 0, 1, 2, -1, -4};//int arr[] = { 0, 0, 0, 0 };//int arr[] = { -2,0,1,1,2 };int arr_len = sizeof(arr) / sizeof(int);vector<int> nums;GeneratorVector(arr, arr_len, nums);my_print1(nums, "目标数组：");Solution s1;vector<vector<int>> result= s1.threeSum(nums);	my_print2(result, "结果：");	system("pause");return 0;
}