leetcode #15#16双指针
1.题目
leetcode #15 3Sum
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.
Example 2:
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.
Constraints:
3 <= nums.length <= 3000
-105 <= nums[i] <= 105
2.解法
这道题的关键是：
- 不能有重复的三元组
- 如何设计出小于O(N^3)时间复杂度的算法
我们的想法是：
nums.sort()//将输入数组进行排序
for first = 0 .. n-1
// 只有和上一次枚举的元素不相同，我们才会进行枚举
if first == 0 or nums[first] != nums[first-1] then
for second = first+1 .. n-1
if second == first+1 or nums[second] != nums[second-1] then
for third = second+1 .. n-1
if third == second+1 or nums[third] != nums[third-1] then
// 判断是否有 a+b+c==0
check(first, second, third)
但是上面这个算法的时间复杂度是O(N^3),我们如何降低时间复杂度？实际上第二层循环和第三层循环可以化成一个循环，假设first固定，我们需要寻找second和third,为了满足nums[second]+nums[third]==-nums[first]这一关系式，second向右移动那么third必须向左移动,这就意味著什么?比如我有两重循环:second从左向右遍历,third从右向左遍历,这个是O(N^2)复杂度的,如果我已经找到一对满足条件的{second,third},那么下一对的的second肯定比之前的大,并且third肯定比之前的小,这就说明third指针不是每次遍历都要从最右边开始，而是third指针每次都从上次的third的位置开始往左遍历，那么对于每层second指针的遍历，third指针都会往左移动若干次，但是当second遍历完后，third指针总共移动的次数是O(N),那么平均一下,每次second指针向右一格,third指针也平均向左移动一格,那么我们就将两重循环降成一重了。
这个方法就是我们常说的双指针，当我们需要枚举数组中的两个元素时，如果我们发现随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法，将枚举的时间复杂度从 O(N^2)减少至 O(N)。为什么是 O(N) 呢？这是因为在枚举的过程每一步中，「左指针」会向右移动一个位置，而「右指针」会向左移动若干个位置，这个与数组的元素有关，但我们知道左指针一共会移动的位置数为 O(N)，均摊下来，每次也向左移动一个位置，因此时间复杂度为 O(N)。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ret;
sort(nums.begin(),nums.end());//排序算法 O(NlogN)
int n=nums.size();
int first=0;
int second=1;
int third=n-1;
while(first<n-2)
{
if(first!=0 &&nums[first]==nums[first-1])
{//第一个数字有重复,寻找新的nums[firt]
first++;
continue;
}
third=n-1;//将右指针初始化成最右边
for(second=first+1;second<n-1;second++)
{//左指针初始化成最左边first+1,下面我们寻找合适的右指针
if(second!=first+1 && nums[second]==nums[second-1])//第二个数字有重复
continue;
while(nums[first]+nums[second]+nums[third]>0 && third>second)
//这句话是右指针的伪循环,因为在下一次进入second循环时,我们没有初始化third
third--;
if(third<=second)//此时说明在first固定下,找到所有的结果了
break;
if(nums[first]+nums[second]+nums[third]==0)
ret.push_back({nums[first],nums[second],nums[third]});
}
first++;
}
return ret;
}
};
3. 再看一道双指针
3Sum Closest
Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.
Return the sum of the three integers.
You may assume that each input would have exactly one solution.
Example 1:
Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
Example 2:
Input: nums = [0,0,0], target = 1
Output: 0
Constraints:
3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-104 <= target <= 104
inline int absnum(int n)
{
if(n>0)
return n;
else
return -n;
}
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int n=nums.size();
sort(nums.begin(),nums.end());
if(nums[0]+nums[1]+nums[2]>=target)
return (nums[0]+nums[1]+nums[2]);
int dist=INT_MAX;
int i,j,k;
int ret;
for(i=0;i<n-2;i++)
{
j=i+1;
k=n-1;
while(j<n-1)
{
if(j>=k) break;
int temp=nums[i]+nums[j]+nums[k];
if(absnum(temp-target)<dist)
{
dist=absnum(temp-target);
ret=temp;
}
if(temp<target)
{
j++;
continue;
}
else if(temp>target)
{
k--;
continue;
}
else
return target;
}
}
return ret;
}
};
总之,双指针的精髓在于,对于双重遍历j,k;虽然每次k移动若干次,但是均摊下来,每次j移动一次,k平均移动一次。
|